C++: Sieve Of Eratosthenes Not Always Working

Question

I am making a C++ program to find prime numbers using the Sieve of Eratosthenes

Currently I have the following code:

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class is_multiple_of {
    int m_div;
public:
    is_multiple_of(int div) : m_div(div) {}
    bool operator()(int n) { return ((n > m_div) && (0 == n % m_div)); }
};

int main ()
{
    vector<int> v;
    for (int i=2; i<=100; i++) v.push_back(i);

    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(2)), v.end() );
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(3)), v.end() ); 
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(5)), v.end() ); 
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(7)), v.end() ); 

    for (unsigned i=0; i<v.size(); ++i)
        cout << v[i] << " ";


    cout << endl << v.size();
    return 0;
}

which works fine i.e. it says there are 25 primes between 1 and 100 (which is correct). However, if i want to know the first 500 primes for example, it will say there are 118 where in reality there are 95. To correct this issue, I have to add more multiples to remove i.e. v.erase( remove_if(v.begin(), v.end(), is_multiple_of(11)), v.end() ); and then add more is_multiple_of()'s.

Is there a way to make this more efficient rather than just having it remove more multiples of previously found primes?

How is your code implementing the Sieve of Eratosthenes (as described in the wiki link) ? — quantdev
It removes all multiples of 2 (evens), then all multiples of 3, followed by 5, then 7, then 11 (you see where this is going) — Bijan
I get what your code does, but it is not implementing the Sieve of Eratosthenes — quantdev
For the Sieve to work you have to remove all primes up to sqrt(n). For n==100 this is 10 but for n==500 this is 19. — uesp

PaulMcKenzie PaulMcKenzie · Accepted Answer · 2014-08-07T22:18:54

Since you want to implement your version of finding the primes, then the following should work (we are using 500)

 int stopInt = static_cast<int>(sqrt(500));
 int j = 0;
 for (int i = 0; i < stopInt; ++i, ++j)
     v.erase(remove_if(v.begin(), v.end(), is_multiple_of(v[j])), v.end());

Here is an alternative that "marks" the items by just moving them to the end of the vector:

     vector<int>::iterator sMarked = v.end();
     int stopInt = static_cast<int>(sqrt(500));
     int j = 0;
     for (int i = 0; i < stopInt; ++i, ++j)
         sMarked = remove_if(v.begin(), sMarked, is_multiple_of(v[j]));
     v.erase(sMarked, v.end());

So we're constantly marking the elements by keeping track of the return value of remove_if. Then at the end, we do one single vector::erase to remove the multiples. This should be more efficient than calling the v_erase constantly in the loop.

C++: Sieve Of Eratosthenes Not Always Working

1 Answers