Eratosthenes

eratosthenes.cpp

/**
 *
 * Eratosthenes of Cyrene.
 *
 */

#include <iostream>
#include <cstdlib>

using namespace std;

namespace Primes {
 
           bool isPrime(int n) {

               int i;

               i = 2;

               bool ok = true;

               while(ok && i*i <= n) {

                     ok = (n % i != 0);

                     i++;
               }

               return ok;
           };
       
          namespace Eratosthenes {

                    void display(int n) {

                         for(int i = 2; i <= n; ++i) {

                             if( Primes::isPrime(i) ) cout<<i<<" ";
                         }

                    } 

                    int getCounts(int n) {

                        bool list[ n + 1 ];

                        int totalPrimes = n - 1;                                     

                        for(int i = 2; i < n + 1; ++i) list[ i ] = true;

                        int i, j;

                        for(i = 2; i * i <= n; i++) {

                                if( list[ i ] ) {

                                    j = 2; 

                                    while(i * j <= n) {

                                          int multiply = i * j;

                                          if( list[multiply] ) {

                                              totalPrimes--;
                                          } 

                                          list[multiply] = false;

                                          j++;
                                    }

                                }
                        }  

                        return totalPrimes;
                    }
          }

};

int main(int argc, char *argv[]) {
    
    int n;
    cin>>n;

    cout<<Primes::Eratosthenes::getCounts(n)<<endl;
    Primes::Eratosthenes::display(n);
    cout<<endl;
    return(0);
}