Sieve of Eratosthenes in C++

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).

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.

• <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.

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 //and since it is odd skip to every other multiple 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.