# Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that by using sqrt instead of pow.

#include<iostream>
#include<math.h>
using namespace std;

int main(){
int number;
cin >> number;
const int CAP = number;
bool * prime = new bool[CAP];

for(int i = 0; i < CAP; i++){ //sets all to true for the marking
prime[i] = true;
}

for(int i = 2; i < number; i++){
if(i <= sqrt(number) && prime[i] == true){
for(int j = i*i; j < number; j++){ //if %i == 0 mark false
if(j % i == 0){               //haven't tried another way
prime[j] = false;
}
}
}
}

for(int i = 2; i < number; i++){
if(prime[i] == true){
cout << i << endl;
}
}

return 0;
}

-

As 200_success pointed out, you have not implemented a sieve. See Wikipedia's pseudo code for the Sieve of Eratosthenes.

You need to check if reading in a number was actually successful:

if (!(std::cin >> number)) {
std::cerr << "Invalid number provided" << std::endl;
return EXIT_FAILURE;
}


(Note that you would need cstdlib for EXIT_FAILURE.)

number is a bad name. It's an int--of course it's a number. What is it's meaning? Get rid of CAP, and name number something more meaningful like maxNumber (or ideally something better -- I'm having a naming mental block).

You should only ever use bare dynamic arrays if you are implementing a container or some other low level structure. They are non-exception safe, and you have to remember to clean up the memory. Just use a pre-allocated vector, and you can retain the same performance (or maybe even better in this relatively rare circumstance).

std::vector<bool> prime(CAP, true);


Note that std::vector<bool> has a specialization that uses packing to save space at the cost of a few extra cycles and some rather odd semantics (you actually get a proxy object from the vector rather than a direct reference to the element).

As Jerry Coffin noted, this task is almost certainly memory constrained rather than CPU, so the higher throughput of bit-based bools should actually provide faster performance.

Also, note that as a bonus on top of automatic memory management, you get to remove your initializing loop.

Though in toy programs it doesn't matter, using namespace std; is considered harmful, and it's a bad habit to form. Instead, use using std::cout;, using std::endl;, etc to only import certain symbols (and do it inside of a function, not at the global level).

It's not technically wrong, but it's much, much more common to use a space between #include and the file:

#include <iostream>


//if %i == 0 mark false this comment says the exact same thing the code does. Either make it much more meaningful (// mark the number non-prime if it is divisible by i), or--better in this situation--just remove it.

Interactive programs should be avoided if at all possible. They cannot be chained with other commands in a scripted fashion, and they are prone to user error. Instead, when you're only accepting one or a few simple user inputs, just use arguments to the program (i.e. use argv to get the maximum number rather than using std::cin).

In C++, if a return value is not specified in main, it is assumed to be EXIT_SUCCESS (0). Because of this, I like to omit return values in main when it's not possible for the program to result in a non successful return. Seeing a return in main makes me immediately wonder if it can fail. (Your program actually should be able to fail, so I would keep the return, you just should also have some error checking on the input reading).

-
For this task, vector<bool> will often be faster than other containers. You lose a little CPU time to isolate one bit of storage, but in exchange you reduce the memory bandwidth by about 8:1. It's normally limited by memory bandwidth, not CPU speed, so (for this task) that typically ends up a win. – Jerry Coffin Apr 1 '14 at 3:51
@JerryCoffin Ah, makes sense I suppose since basically every loop iteration is going to have to pull new data into the cache. Will update accordingly in a moment. – Corbin Apr 1 '14 at 4:34

The title of your post says that you want to implement the Sieve of Eratosthenes. However, your code also performs trial division, and has a sqrt() operation that is typically used as a limit when performing trial division. You should be able to implement the Sieve without doing any division or modulo operation at all. As for the sqrt() limit check, it is superfluous, as the inner loop checks that i * i < number.

-
You're right. I checked the wiki for Sieve of Eratosthenes and it states that it is often confused for trial division. Time to start over again. – Lanyard Mar 31 '14 at 22:46
• <math.h> is a C header. Use the C++ header <cmath>.

• If you have a dynamically-allocated array with new, you must use delete at some point afterwards, otherwise you'll get a memory leak:

delete [] prime;

• When comparing something with a bool, you don't need to explicitly use true or false.

For true:

if (someBool) {}


For false:

if (!someBool) {}

• Do you really need CAP? It's set to the same value as number, except it's const.

• You don't need std::endl in the loop. This also flushes the buffer, which is slower. Instead, use "\n" to produce just a newline.

-
Interesting. I had no idea std::endl was that much slower. When should I use std::endl? – Lanyard Mar 31 '14 at 22:47
@Lanyard: You would usually use at the end of a large output, or if you need to flush the buffer immediately. More info can be found here. – Jamal Mar 31 '14 at 22:49
@Lanyard: My advice would be to never use endl. If you want a new-line, use \n. If you want to flush the stream, I think it's better to pass std:flush to make that intent clear. – Jerry Coffin Apr 1 '14 at 4:00

Here's a function that returns a vector<int> of all the primes up to the given limit. I kept with the dynamic bool array since even a vector seemed to be 4 times slower. There are a number of optimizations that I haven't really seen covered before:

Edit: It appears compiler optimization helps quite a bit. with full optimization the vector is faster. without it's slower.

vector<int> MakePrimes2(int upperlimit)
{
int bound = (int) floor(sqrt(upperlimit));
vector<bool> primes(upperlimit, true);
vector<int> outval;
primes[0] = false;
primes[1] = false;
//Since 2 is a special case if we do it separately we can optimize the rest since
//they will all be odd
for(int i = 4; i < upperlimit; i += 2)
{
primes[i] = false;
}
outval.push_back(2);
//Since the only ones we need to look at are odd we can step by 2
for (int i = 3; i  <= bound; i += 2)
{
if (primes[i])
{
//Since we are looping already we might as well start filling the
//outval vector
outval.push_back(i);
//Since all the even multiples are already accounted for we start
//at the square of the number
for (int j = i*i; j < upperlimit; j += i * 2)
{
primes[j] = false;
}
}
}
//Fill the rest of the vector starting one past the square root of the upperlimit
for(int i = bound+1;i < upperlimit; i++)
{
if(primes[i])
outval.push_back(i);
}
return outval;
}


Returning a vector like this instead of the bool array simplifies your loop to display the list of primes, and is a very minor hit on speed

Update: Did some more tests and using a loop to compare vectors made with my code and with standard code found them to be identical with my method approximately 35% faster finding all the primes up to 1,000,000,000.

-
Can you post your code that used a vector (perhaps a pastebin or gist)? I'm quite surprised that it was slower if your compiler's optimizations were cranked up. Was the vector sized from creation, or grown? – Corbin Apr 1 '14 at 4:43
Same code just replaced the declaration for primes to a vector, vector<bool> primes(upperlimit, true); – tinstaafl Apr 1 '14 at 4:49
On closer look, this has a lot of dubious code in it. It's implied that you're using using namespace std which is fine in implementation files, but without noting that, it's a bit odd. Also, I don't think this function is correct. Have you checked it's output with something like MakePrimes2(1000000)? Also, depending on undefined behavior ("on my compiler...") is questionable. Edit: just realized the bug is likely actually due to the use of undefined behavior. – Corbin Apr 1 '14 at 4:57
I've checked the output against slower but established code and saw nothing wrong and went as high as 100,000,000. I've even used 2 different compiler/ide's and got comparable results. – tinstaafl Apr 1 '14 at 5:04
Seems the vector version is correct (once the extraneous delete[] is removed). The array based version was bugged for compilers (e.g. all of them when optimizations are enabled) that don't zero the array. – Corbin Apr 1 '14 at 5:57