Double factorial and primorial

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Wed Dec 21 10:39:19 CET 2011


Ciao,

Il Lun, 19 Dicembre 2011 6:47 pm, bodrato at mail.dm.unipi.it 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.

Regards,
m

-- 
http://bodrato.it/software/combinatorics.html




More information about the gmp-devel mailing list