blob: 2b2bf2640215c349603c63faebad337302e3cfde (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
constexpr ll N = 100'000'000;
bitset<N / 2> isNotPrime;
vector<ll> primes = {2};
bool isPrime(ll x) {
if (x < 2 || x % 2 == 0) return x == 2;
else return !isNotPrime[x / 2];
}
void primeSieve() {
for (ll i = 3; i < N; i += 2) { // i * i < N reicht für isPrime
if (!isNotPrime[i / 2]) {
primes.push_back(i); // optional
for (ll j = i * i; j < N; j+= 2 * i) {
isNotPrime[j / 2] = 1;
}}}}
|
