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^{2} > 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