Generating primes with Sieve of Eratosthenes
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&lt;int&gt; 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&lt;int&gt;, 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&lt;int&gt;::iterator currentStart = eratosthSieve.begin();
vector&lt;int&gt;::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 &lt; eratosthSieve.end());        
    }
    currentStart = find_if(currentStart + 1, eratosthSieve.end(), isNextStart);
} while (currentNumber &lt; eratosthSieve.end());

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