Originally Posted by CrazyNorman
I found a much faster way of doing this a while back.
Create an array of bools, with "upper_limit" elements, with each one equal to 1.
Then, for each number from 2 to upper_limit, if it is equal to 1, go up by it, setting each value above it, which is a multiple of it equal to 1.
*snip*
Basically, you cross out all the multiples of two. Then all the multiples of three. Then, because four has already been crossed out, you don't cross out its multiples (as they would have already been crossed out by two). Just continue this. Thus, multiples of multiples are not tested.
Its reasonably fast, as it takes it 0.05 seconds to find all primes below 100,000 on my machine.
Its possible to optimize my code further using pointer tricks, but I'll keep it simple for you.
Also, if you do not include the printing of the results to std::cout within the timing, it is so fast that it takes 0 seconds according to the timer I am using.