[math-fun] A faster algorithm for π(x)
Earlier, I had the doc π(n) and the Sieve of Eratosthenes <https://docs.google.com/document/d/1yzj1QZZzmqVG4ow6ScTR5bX5mDOKxNVkQGX7G-HAJfQ/edit>, but I have a better algorithm: This is the same method as in the doc (read the doc and edit it) but we don't add 1 because then it will be hard to compute. What do you think of it? It works, I tried it. -Varun
What is the algorithmic complexity of this technique? What is the complexity if you go ahead and just consider all the primes from sqrt(n) to n as well? Can you improve your algorithm for calculating pi(n)? -tom On Mon, Oct 14, 2019 at 9:31 PM Varun Rajkumar <pi.fermet@gmail.com> wrote:
Earlier, I had the doc π(n) and the Sieve of Eratosthenes < https://docs.google.com/document/d/1yzj1QZZzmqVG4ow6ScTR5bX5mDOKxNVkQGX7G-HA...
, but I have a better algorithm:
This is the same method as in the doc (read the doc and edit it) but we don't add 1 because then it will be hard to compute. What do you think of it? It works, I tried it. -Varun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
participants (2)
-
Tomas Rokicki -
Varun Rajkumar