(29C) Prime numbers up to 10'000

[Albert Chan]

(09-04-2018 06:53 PM)Thomas Klemm Wrote:  A guy called C. Ret did an awesome work ...

What's so cool about it?
Instead of checking if a number is divisible by a prime the odd multiples of the primes
are calculated starting from the square of the prime.

For 7 that would be: 49, 63, 77, 91, 105, …
Or for 11 that would be: 121, 143, 165, 187, …

Of course we can't keep all of them since we have only 30 registers.
But we don't have to. All we need is keeping the smallest among them.

I had a similar (*) code in Lua to build list of primes.
Instead of using min-heap, it uses Lua build-in hash table.

https://github.com/achan001/PrimePi/blob.../prime.lua

(*) main difference is how sequence overlap is treated.
Above sequence for 7 and 11 overlap at 231, 385, 539, 693, ...

C. Ret code carried the prime along, ignoring the overlap.
Lua code skip over the overlap, with the sequence carried the right step.
Both approaches are equivalent.