> What is remarkable about this algorithm is, that it uses no divisions at all!

The same holds for the Sieve of Eratosthenes [1]

[1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

There's a simple combinatorial proof of the existence of a prime between n and n^2:

https://www.quora.com/Is-there-a-prime-between-every-natural...

The gaps between primes are easily produced using two operations on a list of numbers, mirroring and partitioning.

Each prime generates a spacing sequence to find future primes, each prime is effectively casting a new periodic wave function. 2 produces a wave that hits all even numbers. 3 produces a wave that hits every 6 numbers (2 already gets everything else.) 5 does every {20,10}, etc...

You can see the process of generating the sieve waveform, or more technically, the prime gaps, here:

http://math.stackexchange.com/questions/311610/modified-eule...

Look at the 2nd answer, it explains the process. Remember, all prime numbers do, is cast a waveform onto the existing sieve waveform. Just chaotic interference. Division as an immediate reaction to primes is moreso because primes are taught pretty poorly. As mystic nuggets. Rather than chaotic interference.

The coolest technique I know of for checking primes is a variant of the Lucas sequence method (which is what GIMPS uses to find Mersenne primes)[1]. Essentially, you generate terms in a sequence in a constant-memory fashion that doesn't require you to know the factors, using just a modulo in a generating function.

[1]: https://www.youtube.com/watch?v=lEvXcTYqtKU

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.

A long and detailed list of prime number structures in Haskell

https://wiki.haskell.org/Prime_numbers

And a long list of algorithms. Many of which are surprising and probably not that efficient. The first few are:

https://wiki.haskell.org/Prime_numbers_miscellaneous#Prime_W...

Efficiency is kind of a relative issue, since you don't know the job beforehand or which one would be optimal

This is slower than the sieve right?

Given its author, it would be even more remarkable if this algorithm was incorrect. See my comment on the article.