Double factorial and primorial
Niels Möller
nisse at lysator.liu.se
Tue Dec 20 14:36:03 CET 2011
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.
More information about the gmp-devel
mailing list