samedi 26 septembre 2015

Intitutive method to find prime numbers in a range

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