彈吉他寫C++: Sieve of Eratosthenes

2014年2月16日星期日

Sieve of Eratosthenes

Main Goal: Used to list all of primes below and equal to a number

Main Concept: Cross off all the multiples of a number started from 2

For example:
crossing off the multiples of 2
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
then crossing off the multiples of 3
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
then crossing off the multiples of 4 5 6 ... untiil 20
primes are the non-cross-off ones

a little refinement:

not to find all the number's multiple, find the next non-cross-off one as the search base. e.g. after crossing off multiples of 3, next step using 5 as the base rather than 4
the termination condition should not go to 20; it can be stop until the next base is bigger than square root of 20, i.e., it can be stopped when p * p >= 20
the multiple can start further, i.e., the crossing off part can starting on p * p

C++ code:

#include <iostream>
using namespace std;


void sieveOfEratosthenes( int n )
{
    if( n < 2 ){
        cout << "No primes!" << endl;
        return;
    }

    bool *primeFlag = new bool[n+1];
    for( int i = 0 ; i <= n ; i ++ )
        primeFlag[i] = true;

    int p = 2;// next prime number
    while( p*p <= n ){

        // cross-off
        for( int i = p * p ; i <= n ; i += p )
            primeFlag[i] = false; // i is divisible by prime p

        // search for the next prime
        ++p;
        while( p <= n && !primeFlag[p] )
            ++p;

    }

    cout << "Primes below and equal to " << n << ":\n";
    for ( int i = 2 ; i <= n ; i++ )
        if( primeFlag[i] )
            cout << i << " ";
    cout << endl;

}


int main( ){


    cout << "Find all the primes below and equal to n: ";

    int n;
    cin >> n;
    while( n!= -1 ){

        sieveOfEratosthenes( n );

        cout << "\nFind all the primes below and equal to n: ";

        cin >> n;
    }

    cout << "Bye!\n";


    return 0;
}