Generating primes with Sieve of Eratosthenes

There are many problems on the Internet that require you to find prime numbers, so I decided to write a set of functions to find them. I used the Sieve of Eratosthenes for generating the primes as it was fast and easy to implement compared to other algorithms.

However, I'm wondering if my code, rather than my method, is inefficient. Am I using STL containers/iterators correctly? Is there any section in my code slowing down the program?

```
#include
#include
#include
#include
#include
using namespace std;

#define initial_prime_barrier 100
bool isFlagged(int i) { return i == 0; }
bool isNextStart(int i) { return i != 0; }

vector generatePrimesBelow(int limit)
{
vector primes;
for (int i = 2; i ::iterator currentStart = primes.begin();
do
{
int numberAtStart = *currentStart;
vector::iterator currentNumber = currentStart + numberAtStart;
do
{
*currentNumber = 0;
advance(currentNumber, numberAtStart);
} while (currentNumber ::iterator newEnd = remove_if(primes.begin(), primes.end(), isFlagged);
primes.erase(newEnd, primes.end());
return primes;
}

bool isPrime(int number)
{
static vector primes = generatePrimesBelow(initial_prime_barrier);
static int numPrimes = primes.size();
static int largestPrime = primes[numPrimes-1];
static int halfwayPrime = primes[numPrimes/2];
if (number == largestPrime)
{
return true;
}
else if (number halfwayPrime)
{
for (int i = numPrimes/2; i = 0; i--)
{
if (number == primes[i])
{
return true;
}
}
}
}
else if (number > largestPrime)
{
primes = generatePrimesBelow(number + number);
numPrimes = primes.size();
largestPrime = primes[numPrimes-1];
halfwayPrime = primes[numPrimes/2];
return isPrime(number);
}
return false;
}

int main (int argc, char * const argv[])
{
const int number = 123123;
cout << (

I take it you are really hell bent to use STL for everything but maybe you are over using it. However your code as it is, is very redundant. The specific issue I found are:

• Whenever you call isPrime(), you are generating the primes array inside generatePrimesBelow() from scratch. Its not a problem now, but if you call isPrime() from main inside a loop for a couple of numbers, it will be very inefficient.

• Since you are using only one vector for storing both the primes and the sieve, you are using find_if(), remove_if() and erase() which would not be needed if you use 2 vectors for storing the primes and the sieve separately, and hence make the code more efficient.

• In isPrime(), you can simply use the find() function from STL to look whether your number is in primes or not. You don't need to write your own look-up code. Better yet, since the primes is sorted, you can directly use binary_search() STL algorithm on it. But all of this is moot as should search for a number to be prime or not if you have already found whether it is prime or not using generatePrimesBelow().

As per my understanding you can do everything in your isPrime() function itself, including what you are doing in generatePrimesBelow() in lesser lines of code that what your current isPrime() looks like. Here is what you can do:

• Have two vectors, primes and eratosthSieve with eratosthSieve's size being the number - 1 where number was passed in as argument.

-
Use STL generate algorithm to populate eratosthSieve from 2 to number, by having a function passed in as the generating function. It would like like this:

int fillUp() {
    static int i = 1;
    return ++i;
}

and will be used as generate( eratosthSieve.begin(), eratosthSieve.end(), fillUp)

-
Your sieve logic would become something like this with the two vectors:

vector::iterator currentStart = eratosthSieve.begin();
vector::iterator currentNumber;
do 
{
    int numberAtStart = *currentStart;
    if ( numberAtStart != 0 )                 // If the number is 0, it means has been filtered out in the sieve.
    {
        primes.push_back( numberAtStart);
        currentNumber = currentStart + numberAtStart;
        do
        {
            *currentNumber = 0;
            advance(currentNumber, numberAtStart);
        } while (currentNumber < eratosthSieve.end());        
    }
    currentStart = find_if(currentStart + 1, eratosthSieve.end(), isNextStart);
} while (currentNumber < eratosthSieve.end());

-
Check if the last element of the primes vector is equal to number or not:
return ( number == primes.back() );

StackExchange Code Review Q#9306, answer score: 5