[jebediah]

This is slower than the sieve right?

[heinrichhartman]

I think so, but the memory usage is drastically lower: Only O(x/ln(x)) vs. O(x), for getting all primes up to x.

[tromp]

While there are only about x/ln(x) primes, each one takes at least log(x) bits to represent, so there's no memory savings after all.

In fact, there's an increasing loss as we optimize the constant factor in the sieve's O(x).

To wit, Dijkstra's algorithm takes 776MB to store all 203280221 primes under 2^32 at 4 bytes per prime.

A simple version of Eratosthenes' sieve, using 1 bit per odd number, takes 2^31 bits, which is only 256MB.

A more streamlined sieve like the one on my webpage at

http://tromp.github.io/pearls.html

implicitly filters out multiples of 2, 3, and 5, leaving only 8 potential primes in every 30 consecutive integers, conveniently fitting in a byte, for a total of 137MB.

(for some reason, compiling with nonzero optimization gives a gcc 4.8.5 internal compiler error on my SUSE Linux box)

[ableal]

(edit: typo gone, thanks for the interesting write-up)

[heinrichhartman]

Indeed! Thanks a lot. Its corrected now.

... no wait: It's corrected now. ;)