Double factorial and primorial

bodrato at bodrato at
Wed Dec 21 10:39:19 CET 2011


Il Lun, 19 Dicembre 2011 6:47 pm, bodrato at ha scritto:
> Il Lun, 19 Dicembre 2011 10:14 am, Niels Möller ha scritto:
>> Maybe there's no better way to compute the number of primes than to
>> use the sieve of Erathostenes' to generate them all?

> To have the exact count, I believe the only way is generating all primes.

I was wrong.
I'm glancing at the paper "Computing π(x) - the Meissel-Lehmer Method" by
Lagarias, Miller, and Odlyzko (1985), it needs to sieve the range
]1,x^(2/3)] only.



More information about the gmp-devel mailing list