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&lt;iostream&gt;
#include&lt;math.h&gt;
using namespace std;

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

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

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

    for(int i = 2; i &lt; number; i++){
        if(prime[i] == true){
            cout &lt;&lt; i &lt;&lt; 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 &gt;&gt; number)) {
    std::cerr &lt;&lt; "Invalid number provided" &lt;&lt; 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&lt;bool&gt; prime(CAP, true);


Note that std::vector&lt;bool&gt; 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 &lt;iostream&gt;




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