Prime Numbers by Sieve of Eratosthenes

The algorithm works as follows.
1. Create a vector v of consecutive integers {2,3,…,LIMIT}.
2. Select p as the first prime number in the vector v, p=2.
3. Remove all multiples of p from the vector v.
4. set p equal to the next integer in vector v which has not been removed.
5. Repeat steps 3 and 4 until p² > LIMIT, all the remaining numbers in the vector v are prime numbers

More about the algorithm here.

Here’s the c++ code for the algorithm

vector<int> seive(int LIMIT){
    vector<bool> primes(LIMIT, false);
    primes[0]=true;//0 is not prime
    primes[1]=true;//1 is not prime
    int upperSqrt = (int) sqrt(LIMIT);

    for(int i = 2; i <= upperSqrt; i++){
        if (primes[i] == false){
            for (int j = i*i; j <= LIMIT; j+=i){
                primes[j] = true;
            }//end for j
        }//end if
    }//end for i

    vector<int> ret;//vector for holding only prime numbers

    REP(i,primes.size()){
        if(!primes[i]){
            ret.push_back(i);
        }
    }

    return ret;
}

Advertisements