| 7 | int cnt; |
| 8 | |
| 9 | void populateMyPrimes(int N) // i need to find the primes upto root(N) |
| 10 | { |
| 11 | int i=0,j=0; |
| 12 | bool primeArray[DIFF_SIZE]; |
| 13 | for(i=2;i<DIFF_SIZE;i++) |
| 14 | { |
| 15 | primeArray[i]=true; |
| 16 | myPrimes[i]=0;//myPrimes[] array will hold our primes calculated via traditional sieve |
| 17 | } |
| 18 | int myRange=floor(sqrt((double)N)); //we need to calculate prime numbers till myRange |
| 19 | //TRADITIONAL SIEVE STARTS HERE |
| 20 | |
| 21 | int k=floor(sqrt((double)myRange));//to calculate prime numbers till myRange,loop needs to run till sqrt(myRange) |
| 22 | for(i=2;i<=k;i=i++) |
| 23 | { |
| 24 | if(primeArray[i]==true) |
| 25 | { |
| 26 | for(j=i*i;j<=myRange;j=j+i) |
| 27 | { |
| 28 | primeArray[j]=false; // j is a composite number |
| 29 | } |
| 30 | } |
| 31 | } |
| 32 | cnt=0; //stores the number of primes till sqrt(N) |
| 33 | for(i=2;i<=myRange;i++) |
| 34 | { |
| 35 | if(primeArray[i] == true) // false means composite number,true means prime number |
| 36 | { |
| 37 | myPrimes[cnt++]=i; //store the primes in myPrimes[] |
| 38 | } |
| 39 | } |
| 40 | cout<<endl; |
| 41 | } |
| 42 | |
| 43 | int main() |
| 44 | { |