View Single Post
Oct8-09, 12:59 PM
P: 25
I can also compute pi(x) exactly without finding ANY primes smaller than x or sqr(x). It also do not require successive division by primes or the value of a previous pi (y) for y < x. The terms are required to be computed like in:

max {n in IN : 5*7 + 6*5*7(n-1) <= x}

and uses only four constants, all discardable. This is equivalent to computing:

floor ((x - 5*7 + 6*5*7)/6*5*7).

There are many terms however. The formula coefficients needs to be computed and stored in memory.

The method is much simpler than Extended Meissel-Lehmer algorithm but requires more storage space for large x. The storage requirement is of order:

b_4 = 4
b_n = b_(n-1) + n -1

for large n. Can this be written in big O notation?