Feasible implementation of a Prime Counting Function [closed]

Question

What would be a computationally feasible pseudocode of any prime-counting function implementation?

I initially attempted coding the Hardy-Wright algorithm, but its factorials began generating miserable overflows, and many others appear bound to yield similar problems. I've scoured Google for practical solutions, but, at best, have found very esoteric mathematics which I haven't ever seen implemented in conventional programs.

Answer 1

The prime-counting function pi(x) computes the number of primes not exceeding x, and has fascinated mathematicians for centuries. At the beginning of the eighteenth century, Adrien-Marie Legendre gave a formula using an auxiliary function phi(x,a) that counts the numbers not greater than x that are not stricken by sieving with the first a primes; for instance, phi(50,3) = 14 for the numbers 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 49. The phi function can be computed as phi(x,a) = phi(x,a-1) - phi(x/P(a),a-1), where phi(x,1) is the number of odd integers not exceeding x and P(a) is the a-th prime number (counting from P(1)=2).

function phi(x, a)
  if (phi(x, a) is in cache)
    return phi(x, a) from cache
  if (a == 1)
    return (x + 1) // 2
  t := phi(x, a-1) - phi(x // p[a], a-1)
  insert phi(x, a) = t in cache
  return t

An array p stores the a-th prime for small a, calculated by sieving. The cache is important; without it, run time would be exponential. Given phi, Legendre's prime-counting formula is pi(x) = phi(x,a) + a - 1, where a = pi(floor(sqrt(x))). Legendre used his formula to calculate pi(10^6), but he reported 78526 instead of the correct answer of 78498, which, even though wrong, was astonishingly close for an intricate manual calculation.

In the 1950s, Derrick H. Lehmer gave an improved algorithm for counting primes:

function pi(x)
  if (x < limit) return count(primes(x))
  a := pi(root(x, 4)) # fourth root of x
  b := pi(root(x, 2)) # square root of x
  c := pi(root(x, 3)) # cube root of x
  sum := phi(x,a) + (b+a-2) * (b-a+1) / 2
  for i from a+1 to b
    w := x / p[i]
    lim := pi(sqrt(w))
    sum := sum - pi(w)
    if (i <= c)
      for j from i to lim
        sum := sum - pi(w / p[j]) + j - 1
  return sum

For example, pi(10^12) = 37607912018. Even with these algorithms, and their modern variants, and very fast computers, it remains appallingly tedious to calculate large values of pi; at this writing, the largest known value is pi(10^24) = 18435599767349200867866.

To use this algorithm to calculate the n-th prime, a corollary to the Prime Number Theorem bounds the n-th prime P(n) between n log n and n(log n + log log n) for n > 5, so compute pi at the bounds and use bisection to determine the n-th prime, switching to sieving when the bounds are close.

I discuss prime numbers in several entries at my blog.

Answer 2

Wikipedia might help too. The article on prime counting contains a few pointers. For starters I'd recommend the algorithm by Meissel in the section "Algorithms for evaluating π(x)", which is one of simplest algorithm that does not generate all primes.

I also find the book by Pomerance and Crandall "Prime numbers a computational perspective" helpful. This book has a detailed and quite accessible description of prime counting methods. But keep in mind that the topic by its nature is a bit too advanced for most of the reader here.