Double factorial and primorial

Niels Möller nisse at
Thu Dec 22 08:05:40 CET 2011

Torbjorn Granlund <tg at> writes:

> I implemented a variant where all primes live in the heap, perhaps
> exactly what Niels suggested.


> 95% of the time is spent in heap_remove, unsurprisingly.

And to decrease the heap work, one could keep the small primes in an
array outside of the heap (as you suggested). Or use a larger sieving
table. Or use a more compact representation to fit more numbers in the
same space (at the cost of some additional bit fiddling).

Do you have any intuition on what additional speedup one could get with
such tricks?


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