Hacker News new | past | comments | ask | show | jobs | submit login

You'll be happy to know that computers can go even faster, and it doesn't need anywhere near 3.5 (= 115e6/33e6) bytes per number: you can use a single bit for each one (3.9 MiB), or only store numbers that aren't obviously composite (e.g. only odd numbers gives half that, and using a 30-wheel gives 1.0 MiB).

In any case, you can do a lot better than merely 33 million: e.g. http://primesieve.org/ uses some seriously optimised code and parallelism to count the primes below some number between 10 billion and 100 billion in a streaming fashion (meaning very small memory use). For non-streaming/caching the results, I'm not sure how primesieve does, but my own primal[0] (which is heavily inspired by primesieve) can find the primes below 5 billion and store everything in memory in 1 second using ~170 MiB of RAM on my laptop (and it doesn't support any parallelism, at the moment), and the primes below 500 million in ~0.75 seconds on a Nexus 5, and ~1 second on a Nexus S (although both devices give very inconsistent timings).

[0]: https://github.com/huonw/primal




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: