Harristotelian Logic

Oh, I just thought of something.

My prime counting function in its sieve form is what I've given quite a few times before.

With natural numbers x and n, where p_i is the i_th prime:

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

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

Notice that qualification that if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

But if n is the count of primes up to and including sqrt(x), then P(x,n) = pi(x).

So for fast coding since you have a cache of primes anyway, you just directly grab the value of pi(x) if you have it, and yes, then, my prime counting function in its sieve form—even without the additional optimizations I talked about—is MUCH faster than Legendre's.

So I was right before noting it's faster—unless someone codes it dumb and iterates back through when you can use pi(x) and the primes already in memory, as you need the primes up to sqrt(x).

My PrimeCountH.java takes that a step further and actually uses a bigger sieving than necessary so it stores more primes than there are up to and including sqrt(x).

It also has a nifty implementation of a search algorithm to go find those primes quickly.

So Tim Peters could match my prime counting function against Legendre's and get the same speed ONLY by stupidly coding the top iterations.