While trying to find prime numbers in a range (http://ift.tt/1eOf6my)
I came through this solution but I didn't find this code intutive and not easy to derive out.What could be the alternative to mark non-prime numbers in a range .Following is the code snippet which I am unable to understand
This is source from I which I referred the code http://ift.tt/1iT8FlR
for(i=0;i<cnt;i++) //for each prime in sqrt(N) we need to use it in the segmented sieve process
{
p=myPrimes[i]; //store the prime
s=M/p;
s=s*p; //the closest number less than M that is a composite number for this prime p
for(int j=s;j<=N;j=j+p)
{
if(j<M) continue; //because composite numbers less than M are of no concern to use.
primesNow[j-M]=false;/*j-M = index in the array primesNow,this is because max index allowed in the array
is not N ,it is DIFF_SIZE so we are storing the numbers offset from
while printing we will add M and print to get the actual number*/
}
}
for(int i=0;i<cnt;i++) //in the above loop the first prime numbers for example say 2,3 are also set to false
{ //hence we need to print them in case they are within range.
if(myPrimes[i]>=M && myPrimes[i]<=N) //without this loop you will see that for an range(1,30), 2 and 3 does
cout<<myPrimes[i]<<endl; //not get printed
}
for(int i=0;i<N-M+1;++i) // primesNow[]=false for all composite numbers,so prime numbers can be found by checking with true
{
if(primesNow[i] == true && (i+M)!=1) //i+M != 1 to ensure that for i=0 and M=1 , 1 is not considered a prime number
cout<<i+M<<endl; //print our prime numbers in the range
}}
Aucun commentaire:
Enregistrer un commentaire