Double factorial and primorial

Torbjorn Granlund tg at
Thu Dec 22 06:49:19 CET 2011

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

It is just proof-of-concept code, and the initial prime table is made
naively using trial division.  After that, there is no division or

This code computes all primes < 10^9 in 2s (on a Phenom II 3.2 GHz).
That is about 40 times faster than the current gmp_nextprime code.

The comparison is quite unfair, since the new code has no "nextprime"
interface.  It also uses 100 times more memory.

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ehsieve.c
Type: application/octet-stream
Size: 3835 bytes
Desc: not available
URL: <>
-------------- next part --------------


More information about the gmp-devel mailing list