blob: 68f7fcb743dfd42785777dd1bb33c97a3931a4e7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
constexpr ll N = 100000000;
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() {
// i * i < N is enough for isPrime
for (ll i = 3; i < N; i += 2) {
if (!isNotPrime[i / 2]) {
primes.push_back(i);
for (ll j = i * i; j < N; j+= 2 * i) {
isNotPrime[j / 2] = 1;
}}}}
|
