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 p2 > 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