Counting Primes Using Legendre’s Formula July 22, 2011 The
prime-counting function π(n) computes the number of primes not
greater than n, and has been a matter of fascination to
mathematicians for centuries. The Prime Number Theorem tells us
that π(n) is approximately n / log(n); Carl Fredrich Gauss
proposed the prime number theorem in 1792 when he was only
fifteen years old, and Jacques Hadamard and Charles-Jean de la
Valle Poussin both proved it, independently, in 1896. The first
person to make a serious attempt at the calculation, except for
trivial attempts that simply enumerated the primes and counted
them, was the French mathematician Adrien-Marie Legendre at the
end of the eighteenth century; his formula was correct, but he
erroneously reported that π(106) = 78526, whereas the correct
value is 78498. We will recreate Legendre’s calculation in
today’s exercise. Legendre’s formula works in two parts. First,
he defined a function φ(x, a) that counts all the numbers from 1
to x inclusive that are not stric