View Single Post
 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?