Hello everyone.
I'm a little surprised that nobody said it, but such function is known.
It is called Pi(x), and gives the number of primes less than x. The main
problem is the implementation of Pi(x), of course.
Maybe the algorithm developed by Allen is new, but there are some other
algorithms used.
For example, the software Mathematica implements the function
PrimePi[n], and the help says:
"PrimePi use sparse caching and sieving. For large a, the
Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on
asymptotic estimates of the density of primes."
It works with an n up to about 8*10^13 and it is very fast.
For example, with the number of Allen, (200,000,093):
PrimePi[200000093] //Timing
{0. Second, 11078945}
You can find much more information and references here:
http://mathworld.wolfram.com/PrimeCountingFunction.html
Regards.
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
