# Sieve of Eratosthenes in C++11

Please point out every problem you see with this code. Any fundamental flaws, naming conventions, design decisions, you name it.

#include <iostream>
#include <algorithm>
#include <vector>

class SieveHelper {
public:
SieveHelper() : cur(2) {}

bool operator()(unsigned int i) {
return i != cur && i % cur == 0;
}

unsigned int cur;
};

void sieve(std::vector<unsigned int>& arr) {
SieveHelper helper;
auto it = arr.begin();

while (it != arr.end()) {
helper.cur = *it;

auto last = std::remove_if(it, arr.end(), helper);
arr.erase(last, arr.end());

it++;
}
}

int main() {
int n;
std::cin >> n;

std::vector<unsigned int> arr(n);
for (int i = 2; i <= n; i++)
arr[i-2] = i;

sieve(arr);

std::for_each(arr.begin(), arr.end(), [](unsigned int i) {
std::cout << i << " ";
});
return 0;
}

• A classical prime sieve is probably not implemented in terms of erasing from a vector. ideone.com/8yKTK is an example, optimized for minimizing memory usage. sieve_vec is a table of booleans where indexes correspond to odd values 1, 3, 5, 7, ... – UncleBens Dec 29 '11 at 15:23
• As to difference in speed compare ideone.com/MB3VJ (primes up to 10,000,000 in 0.08 seconds) and ideone.com/BKQXd (up to 200,000 in 2.5 seconds). – UncleBens Dec 29 '11 at 15:31

• I sort includes alphabetically, making it easier to keep track of which headers are included in long lists.

I would write:

#include <algorithm>
#include <iostream>
#include <vector>


In a long, unsorted list of includes it's hard to see if a header is included twice:

#include <vector>
#include <list>
#include <algorithm>
#include <new>
#include <fstream>
#include <set>
#include <stdexcept>
#include <list>
#include <cstdlib>


Imagine this problem increasing if you have a couple dozen includes!

• arr is very undescriptive, and in this case even misleading. This isn't an array, it's a std::vector. vec would be slightly better, but try to describe what the data structure contains or does rather than what kind of data structure it is. Even something as simple as numbers is better than vec (or arr), and you can probably improve that even further. Naming is very important to ensure readability.
• Consider using <cstdint> to control the size of numbers. This makes porting a whole lot easier.
• In C++, it's a good habit to prefer prefix increment- and decrement-operators, because they are usually more efficient for non-built-in types. It doesn't really matter for built-in types, but consistency is nice.
• Consider using using-declarations, i.e. using std::vector; and so on, to make the code more readable.
• I'd usually make SieveHelper::cur private and control access to it, but I presume you know that and did it this way on purpose. It's fine for a small program, but remember that programs grow.
• Use std::vector::at(), which is bounds-checked, whenever array indexing is not in the speed-critical path. The exception is when you're 110 % sure you can never, ever go out of bounds - but better safe than sorry!
• Consider making sieve() take and return an argument, rather than just manipulate an output argument. This is definitely a trade-off, so use your own judgement, but output parameters are generally less readable.

On the plus side, this is mostly good. Extra points for using built-in algorithms, lambda and other juicy C++11 stuff :)

• don't agree with using at() as default. I would prefer operator[] as default using at() only when data comes from user (unvalidated input). If you can't guarantee the values on validated code then you have bigger problems. – Martin York Dec 30 '11 at 2:36
• @LokiAstari I agree that you should never actually have an exception thrown from at() - but that means even more reason to use it, because its cost is then practically the same as operator[]. However, if you do get an exception from at(), then it's much easier to debug. Also, we should swallow our hubris and write robust code when we can ;) – Lstor Dec 30 '11 at 8:32

Where you use while() I would prefer to use for(;;) (and use pre-increment).
Not a big deal but I like to keep all the loop control in one place

auto it = arr.begin();

while (it != arr.end()) {
// STUFF

it++;
}

// I prefer (though not much different)

for(auto it = arr.begin(); it != arr.end(); ++it)
{
// STUFF
}


Rather than have SieveHelper being declared once and then updated each time through the loop. Just create a new one each iteration. The actual cost of construction will be optimized to zero and it becomes easier to read.

    helper.cur = *it;

auto last = std::remove_if(it, arr.end(), helper);

// I would do this (note it requires slight modifications to SieveHelper (see below)).

auto last = std::remove_if(it, arr.end(), SieveHelper(*it));


Keeping const correct is a good habit to get into. You need to apply this to your SieveHelper. Also for simple helper functions like this I like to make them structs

struct SieveHelper
{
bool operator()(unsigned int i) const  // object not changed by method => const
//                              ^^^^^
{
return i != cur && i % cur == 0;
}

// Use a reference (as we don't need to store state in the helper)
SieveHelper(unsigned int const& c) : cur(c) {}
private:
unsigned int const&  cur;
};


Since you are using C++11 we can even simplify this to a lambda

auto last = std::remove_if(it, arr.end(),
[&it](unsigned int i){ return i != (*it) && i % (*it) == 0;}
);


As an optimization (probably not a big one) you don't need to call erase after each iteration:

void sieve(std::vector<unsigned int>& arr)
{
SieveHelper helper;
auto it   = arr.begin();
auto last = arr.end()

while (it != arr.end()) {
helper.cur = *it;

last = std::remove_if(it, last, helper);

it++;
}
arr.erase(last, arr.end());
}


Now if we apply all these (apart from lambda)

void sieve(std::vector<unsigned int>& arr)
{
auto last = arr.end()

for(auto it = arr.begin(); it != arr.end(); ++it)
{
last = std::remove_if(it, last, SieveHelper(*it));
}
arr.erase(last, arr.end());
}

• Good comments, and I also prefer for over while. While while may be more readable, it spills a variable into the surrounding scope, and with while it's easier to neglect the incrementing statement. – Lstor Dec 30 '11 at 8:37
• Wow, I'm really glad you came in and replied even after I already chose an answer because this is really great! Any chance you could point me to an article about the particular compiler optimization on constructing each iteration? – flumpb Dec 30 '11 at 17:43
• Sorry I don;t have an article. You should be able to see it by generating and examining the assembly produced. – Martin York Dec 30 '11 at 19:03

Why are you adding 1 to your array?

I can give a simple performance hint. You know that every even number except 2 is composite, so in initialization of arr do not add even numbers (and of course you should not check for 2 in your sieve function). Something like this:

std::vector<unsigned int> arr(n/2+1);
arr[0] = 2;
for (int i = 3; i <= n; i+=2)
arr[i/2] = i;


or you can go further and do not add multiples of 2 and 3. For walking over numbers which are not multiples of 2 and 3, you should first take a step of size 2 and then take a step of size 4 and again 2 and again 4 and ...

std::vector<unsigned int> arr(n/3+1);
arr[0] = 2;
arr[1] = 3;
int t = 2;
for (int i = 5; i <= n; i+=t, t=6-t)
arr[i/3+1] = i;

• Thank you for pointing out the 1. I removed that from the above code. – flumpb Dec 29 '11 at 16:39

I like closing for and if one liners just to prevent accidental addition of code that doesn't get executed or put the entire thing on one line, but that may just be me.

for (int i = 2; i <= n; i++) {arr[i-2] = i;}


or

for (int i = 2; i <= n; i++) {
arr[i-2] = i;
}


Since this still gets listed near the top rank under "Sieve of Eratosthenes": the code under review does not implement the Sieve of Eratosthenes at all, it is trial division pure and simple.

The real Sieve of Eratosthenes avoids division, and that makes it orders of magnitude faster. Even millions of times when numbers get big enough.

The wikipedia article for SoE explains it well, and there are plenty of code examples for it at Rosetta Code in many languages. A couple more are on this page.

The best overview from a programmer's perspective is probably Achim Flammenkamp's page.