Double factorial and primorial

Niels Möller nisse at
Tue Dec 20 08:30:13 CET 2011

bodrato at writes:

> If we really want a prime_count function in GMP I can write a more clever one

I don't know how important that is. Long-term, I think gmp should at
least export some sieving functionality which us suitable as a building
block for that.

>>> counting the primes in [1,2^34] required half the time of
>>> (sieving and) multiplying all primes in [1,3*2^28].
>> So sieving is a significant part of the work for the primorial function.
> Counting primes in [1,3*2^28] is 1/60 than counting in [1,2^34], i.e.
> 1/120 of the time to compute primorial(3*2^28).

Ooops, I didn't notice that you had very different intervals in that


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