Segmented Sieve

Segmented Sieve [ Number Theory ]

Zobayer Blog

Implementation 01:

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include<bits/stdc++.h> using namespace std; #define MAX 100009 typedef long long ll; vector<int>primes; void seiveOfEratosthenes() { bool flag[MAX+1]; for(int i = 0; i <= MAX; i++) flag[i] = true; primes.push_back(2); flag[0] = flag[1] = false; for(int i = 4; i <= MAX; i += 2) flag[i] = false; for(int i = 3; i <= MAX; i += 2){ if(flag[i] == true){ // i is prime primes.push_back(i); for(int j = i+i; j <= MAX; j = j+i){ flag[j] = false; // j is not prime } } } } void segmentedSeive(ll L, ll R) { bool isPrime[R-L+1]; for(int i = 0; i <= (R-L+1); i++) isPrime[i] = true; if(L == 1)isPrime[0] = false;  for(int i = 0; i < (int)primes.size() && primes[i]*primes[i] <= R; i++){ ll curPrime = primes[i]; ll base = curPrime * curPrime; if(base < L){ base = ( (L+curPrime - 1)/curPrime)*curPrime; } for(ll j = base; j <= R; j += curPrime) isPrime[j - L] = false; } for(int i = 0; i <= R - L; i++){ if(isPrime[i] == true) cout << L + i << endl; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock(); seiveOfEratosthenes(); ll L,R; cin >> L >> R; segmentedSeive(L,R); return 0; double end_time = clock(); // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Implementation 02:

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

#include<bits/stdc++.h> using namespace std; #define MAX 46656 #define LMT 216 #define LEN 4830 #define RNG 100032 unsigned base[MAX/64], segment[RNG/64], primes[LEN]; #define sq(x) ((x)*(x)); #define mset(x,v) memset(x,v,sizeof(x)) #define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31))) #define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31))) typedef long long ll; //Generates all the necessary prime numbers and marks them in base. void seive() { unsigned i,j,k; for(i = 3; i < LMT; i += 2) if(!chkC(base, i)) for(j = (i * i), k = (i << 1); j < MAX; j += k) setC(base, j); for(i = 3, j = 0; i < MAX; i += 2) if(!chkC(base, i)) primes[j++] = i; } // Returns the prime-count within range [a,b] and marks them in sement. int segmentedSeive(int a, int b) { unsigned i,j,k, cnt = (a <= 2 && 2 <= b) ? 1 : 0; if(b < 2) return 0; if(a < 3) a = 3; if(a%2 == 0)a++; mset(segment,0); for(i = 0; ( primes[i] * primes[i] ) <= b; i++){ j = primes[i] * ((a + primes[i] - 1) / primes[i]); if(j%2 == 0) j += primes[i]; for(k = (primes[i] << 1); j <= b; j += k) if(j != primes[i]) setC(segment, (j-a)); } for(i = 0; i <= (b - a); i += 2) if(!chkC(segment, i)){ cnt++; } return cnt; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock(); seive(); int L,R; cin >> L >> R; cout << segmentedSeive(L,R)<<endl; return 0; double end_time = clock(); // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Share: