4 ms·

This is slower than the sieve right?

• heinrichhartman 10y ago
  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.
  • ableal 10y ago
    (edit: typo gone, thanks for the interesting write-up)
    • heinrichhartman 10y ago
      Indeed! Thanks a lot. Its corrected now. ... no wait: It's corrected now. ;)
  • tromp 10y ago
    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 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)