Counting primes, posting again

Turns out possibly the best available way to learn how to count prime numbers is also one of the easiest to show.

With ints or longs--where p_j is the jth prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/p_j,j-1) - (j-1)}

That summation will count primes if you make sure n equals the count of primes up to sqrt(x), but no higher.

There is nothing else discovered that is as simple that is also as fast.

An example of it counting primes is with P(100,4) = 25. So then it counts primes up to 100, where there are 25, and needs to be told the primes up to sqrt(100) = 10, and there are 4 of them. And those primes are: 2, 3, 5 and 7.

That's using the form where it needs to be told the primes up to sqrt(x), but you can fully mathematicize it into a form where it finds them on its own. But that slows it down and it looks a little more complicated.

And I've posted about it before.

Have had it for over a decade. Came across it as a problem solving thing, just started thinking to myself about counting prime numbers.


James Harris