## Counting Primes

### February 9, 2016

We have studied functions for counting the prime numbers less than a given number in two previous exercises. All of them were based on Legendre’s phi function that counts the numbers less than *x* not stricken by sieving with the first *a* primes.

Today we look at a rather different method of counting the primes that is due to G. H. Hardy and Edward M. Wright. Their method is based on factorials, and their formula is

for *n* > 3, where ⌊*n*⌋ is the greatest integer less than *n*. The expression inside the big parentheses is 1 when *n* is prime and 0 when *n* is composite, by Wilson’s Theorem, which states that an integer *n* > 1 is prime if and only if (*n* − 1)! ≡ −1 (mod *n*); the theorem was first stated by Ibn al-Haytham (c. 1000AD), but is named for John Wilson, who first published it in 1770, and it was first proved by Lagrange in 1771.

Your task is to write a program that counts primes by the Hardy-Wright method. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Very interesting algo, albeit somewhat impractical. It was a good refresher though for the BigInt type (Julia language) that makes it usable for inputs over 23.

My previous comment has a solution in Common Lisp.

Two Scheme implementations, or one in two ways. I felt quite stupid for quite a while before I understood that I want to update the factorial with j-1 instead of j-2 when I also update j. (Now I don’t understand why the model implementation also works :)