![]() |
|
|
#1 |
|
2·7·11·61 Posts |
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 |
|
![]() |
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 |