-
Notifications
You must be signed in to change notification settings - Fork 0
/
segmented_sieve.cpp
41 lines (40 loc) · 972 Bytes
/
segmented_sieve.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* segmented sieve */
const int MAXN = 1e6;
vector<int> primes;
int isPrime[MAXN]; //isPrime[i] = 0 indicates i is prime.
void sieve(){
//if even check itself while calling. This function will only tells wether a number is prime or not(not for even numbers).
isPrime[0] = isPrime[1] = 1;
primes.pb(2);
for(int i = 3; i <= MAXN; i+=2){
if(isPrime[i] == 0){
primes.pb(i);
if(i*(ll)1*i <= MAXN){
for(int j = i*i; j <= MAXN; j += (2*i)){
isPrime[j] = 1;
}
}
}
}
}
const int SIZE = (int)1e6+1; //define size to be max(B-A+1)
int arr[SIZE];
void segmentedSieve(int a, int b){
memset(arr, 0, sizeof(arr));
if(a == 1) a++;
int sqrtn = sqrt(b);
//arr[0] represents a
for(int i = 0;i < primes.size() && primes[i] <= sqrtn; i++){
int p = primes[i];
int j = p*p;
if(j < a) j = ((a+p-1)/p)*p; //j = ceil(a/p)*p
for(; j <= b; j+=p)
arr[j-a] = 1;
}
int res = 0;
for(int i = a; i<= b; i++){
if(arr[i-a] == 0)
pi(i);
}
return;
}