News for hackers. Stuff that matters.
Re:Dijkstra's Prime Number Algorithm by kmill on Tuesday April 05, 2016 @05:08PM (#11434469)
This algorithm seems similar to one I found* which is a Sieve of Eratosthenes that doesn't require deciding how big of an array to allocate at the beginning. Essentially, you reverse the order of the two main loops, modifying the main data structure accordingly.

http://www.kylem.net/stuff/sieve_eratosthenes.html

I don't completely understand it yet, but I think the Dijkstra version might have optimized the structure which contains the multiples of known primes, where I just put it into a dictionary.

* I initially saw it in a paper about how the Sieve is generally implemented incorrectly in Haskell, but I made a small Python generator implementation.

There are no comments on this comment yet.