Sunday 17 July 2016

Sieve of Eratosthenes - Count of prime numbers till a given number

/* Count the number of prime numbers less than a non-negative number, n. */
/* Method : Sieve of Eratosthenes */


 #include <iostream>  
 #include <cmath>  
 using namespace std;  
 int main(){  
   int N = 6;  
   int primesCount = 0;  
   int *arr = new int[N + 1];  
   for(int i = 0; i <= N; i++){  
     arr[i] = 1;  
   }  
   arr[0] = 0;  
   arr[1] = 0;  
   for(int i = 2; i <= sqrt(N); i++){  
     if(arr[i]){  
       for(int j = i * i; j <= N; j = j + i){  
         arr[j] = 0;  
       }  
     }  
   }  
   for(int i = 0; i <= N; i++){  
     if(arr[i]){  
       primesCount++;  
     }  
   }  
   cout << primesCount << endl;  
   return 0;  
 }  
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive