Prime Counter

An early mathematical result of mine was my own prime counting function.

With natural numbers--means use 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)}

It counts primes when n equals the count of primes up to sqrt(x), so if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

To see an example of it used click here.

For say, the count of primes up to 100, if you tried P(100,10), the algorithm would reset n to n=4, so you'd have P(100,4), because there are 4 primes--2, 3, 5 and 7--up to sqrt(100), and the answer of course is 25. The algorithm is fairly easy to program.

An innovation of mine was to use a two-variable function where math people traditionally use a single variable one.

If you're curious about more of the underlying mathematics--warning is a good deal more abstruse--you can go to a post of mine on my math blog.


James Harris