Double factorial and primorial

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> then one could sort the indexes using a minheap.

Clever!

That would give the following algorithm for generating primes up to n:

1. Generate a list of all primes p_k up to sqrt(n).

2. Create a minheap which for each k contains the smallest odd multiple
   of p_k which is larger than sqrt(n), together with a link to p_k (can
   this be optimized? I think we should be able to get away without lots
   of divisions. E.g, for those k for which p_k^2 > sqrt(n), we can put
   these squares into the heap rather than the *smallest* multiple.

3. Repeatedly extract and modify the smallest element of the heap. This
   gives us all (odd) composite numbers in the range sqrt(n), n, and any
   missing numbers are the primes, in order.

Is this faster than doing the sieving blockwise using a bitmap? We get a
very different memory access pattern. It might lose big if the heap (of
size sqrt(n)) doesn't fit in the cache. I don't know how bad locality
you typically get with a heap.

/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.