At 12:58 AM 10/13/2006, Allen Poapst wrote: >My formula uses minimally all primes smaller or equal to the sqrt(x) to give >an accurate solution to pi(x). I am not sure if there is an accurate formula >for pi(x) which ALWAYS works, if there is than even the math profs at my >school have not heard of it.
Hi Allen, Although you sent your first message some time ago, it appears that you haven't received much information about the long history of methods for computing pi(x). I hope you will find some of the following to be of use. Your description of your formula sounds very much like Legendre's formula, which has been known for about two hundred years; it too requires knowledge of the primes up to sqrt(x). More efficient formulas of a similar type were developed by Meissel and Lehmer, requiring knowledge of the primes only up to the cube root of x. These methods are described in detail in the first chapter of Hans Riesel's book, _Prime Numbers and Computer Methods for Factorization_, along with a few others. Still better methods have been developed in the past two decades; using these, the exact number of primes less than 4*10^22 has been determined. (See http://primes.utm.edu/howmany.shtml .) There are indeed "formulas" for pi(n) (see http://primes.utm.edu/notes/faq/p_n.html and http://en.wikipedia.org/wiki/Prime_formula ), but they generally work by encoding the computations for some standard method of detecting primes (trial division, or, even worse, Wilson's theorem) into a summation. They're not a practical means of computing anything, but they do exist. Hope that helps. -- Fred W. Helenius [EMAIL PROTECTED] _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
