Spoj problem Prime1(segmented sieve)

Revision en1, by n8118, 2015-06-09 22:57:59

I have been trying to solve a problem on segmented sieve i.e prime1(http://www.spoj.com/problems/PRIME1/) in spoj but i am getting wrong answer and unable to find the bug in the code. So please help me..

include

include

include

include

define lli long long int

define inf 10000000001

using namespace std; int count[1000001]; int store[88888]; int main() { int p = 2,d = 0; lli n = sqrt(inf); while (p <= n) { store[d++] = p; for (lli j = 2; j <= n/p; j++) { count[p*j] = 1; } int l; for (l = p + 1; l <= n; l++) { if (count[l] == 0) { p = l; break; } } if (l == n + 1) { break; } } int t; scanf("%d",&t); while (t--) { int l,r,x = 0,ct = 0; scanf("%d %d",&l,&r); map <int,int> m1; p = store[x]; while (x < d && p <= sqrt(r)) { int z = l/p; if (l % p == 0) { m1[l] = 1; } if (l <= p) { z = 1; } for (int i = z+1; i <= r/p; i++) { m1[p*i] = 1; } p = store[++x]; } for (int i = l; i <= r; i++) { if (i == 1) { continue; } if (m1[i] == 0) { printf("%d\n",i); } } printf("\n"); } return 0; }

Tags spoj, primes, sieve of eratosthenes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English n8118 2015-06-09 23:01:01 970
en1 English n8118 2015-06-09 22:57:59 1221 Initial revision (published)