I need to write a program in C++ that finds all primes up to 2^32. I used a Sieve of Eratosthenes with multiple threads, but it only worked well up to about 10 million. After that it just takes too long. Sometimes it would even crash. I'm wondering if it's my code that needs fixing, or if it's just a bad idea to use Sieve of Eratosthenes with that big a number? What are better prime sieves for large numbers? I've read about some other ones, but can't find anywhere that says which are good for larger ranges.
[Math] Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N
algorithmsprime numberssieve-theory
Related Solutions
I bet no one can calculate a number higher then 250 trillion to be prime with the sieve of eratosthenes
That is just false. Are you going all the way to $n$ instead of $\sqrt{n}$ when looking for factors?
The first time I ever used java, (which usually isn't noted for its computational prowess) for fun I wrote a silly program that would factor a number $n$ by checking all the odd numbers up to $\sqrt{n}$. (This is my version of "Hello World!")
This is strictly worse then the eratosthenes sieve, and took longest for prime numbers, but it was able to detect primality for numbers up to $9\times 10^{19}$ in less than a second. The only reason it couldn't check larger numbers was because java's "long" only goes up to $9\times 10^{19}.$
So if this trivial program on a old computer using java can check numbers that are $12$ orders of magnitude larger than yours, and $5$ orders of magnitude larger than your theoretical upper bound, there must be a problem with how you are implementing these methods.
Fun note: I never have forgotten that from this program, the number $1234567898765432111$ is prime.
What you are looking for is a computational function that returns the list of primes less than 1000, and works as efficiently as possible, on just that problem.
There are 168 primes between 1 and 1000, so any method will take at least 168 operations, obviously.
Suppose you could find approximately a list of 13 numbers and a disjoint other list of 13 numbers, such that precisely every prime occurs when you sum the two sets together elementwise, and no more than that (no composites; otherwise more testing would be required to filter them out).
What I mean is:
$$ A := \{0, 2, 6\} \\ B := \{5, 11, 17\} \\ A + B = \{ 5, 11, 17, 7, 13, 19, 23\} $$
You can most likely find two sets of around 13-20 elements each such that when you sum the sets you get your list. The sets would then be constants in your program, and the program that generates your output in under 200 operations, actually in 169 arithmetic operations (less if you're allowed to include $B$ which could be made to be all prime numbers if there's a $0$ included in $A$).
See:
Best Answer
The Sieve of Eratosthenes is very good in that range, so it's probably your implementation. But why roll your own? There are excellent implementations out there: