mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-08-25, 20:18   #1
nmckenzie
 

2·7·11·61 Posts
Default CountPrimes in O(n^2/3 ln n) time- Linnik's Ident

I have no idea if this is the sort of thing you folks are interested in this, but I've put up online a (as far as I know) new algorithm for computing pi(n), the number of primes less than some number n, in O(n^2/3 ln n) time and O(n^1/3 ln n) space, based on an identity first found by Yuri Linnik that connects prime numbers to the strict count of divisor functions, and then a bunch of elbow grease on my part...

The approach is not related to either the extended Meissel-Lehmer approach, nor to the analytic method Lagarais-Odlyzko. It does, however, have some deep similarities to (and was inspired in part by) an approach for computing Mertens function from Deleglise and Rivat.

The algorithm and working code can be found here: http://www.icecreambreakfast.com/pri...ecounting.html

If you have any suggestions about what I might do with this, or if there are more appropriate places to try to ask around about such a thing, I'd really appreciate it.

Thanks!
Nathan McKenzie
  Reply With Quote
Reply



Similar Threads
Thread Thread Starter Forum Replies Last Post
Time to End davar55 Lounge 4 2013-02-23 02:40
How much time Unregistered Information & Answers 4 2008-12-20 21:00
New .dat time? benjackson Prime Sierpinski Project 16 2008-07-29 07:26
Time Xyzzy Science & Technology 26 2008-01-19 03:28
P3 TF time PrimeCruncher Software 30 2003-12-21 05:26

All times are UTC. The time now is 15:57.


Mon Aug 2 15:57:33 UTC 2021 up 10 days, 10:26, 0 users, load averages: 2.00, 2.09, 2.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.