Harristotelian Logic

Well, wouldn't you know that Tim Peters and his supporters whined all over the place in the thread with my previous code challenge, and it seems like it is just not a fair test—according to them—for him to have to code in Python an equal speed or faster prime counting algorithm against my code already done in Java.

See:
http://groups-beta.google.com/group/extrememathematics/web/counting-primes

So I have a new test.

See, I am a fair person and I want to help Tim Peters out.

His claim is that optimizations to my prime counting function are equivalent to optimizations to Legendre's Method.

My prime counting function in its sieve form is as follows.

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.

It can be immediately sped up by using the following.

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

P(x,n) = x - floor(x/2) - 1 - sum for i=2 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.

That may not seem like much to many of you and I noticed a post where Peters claims that you can just speed up Legendre's Method the same way, so the challenge is simple:

He is to code an implementation in Python of the speed-up of my prime counting function, do the same with Legendre's in the way he thinks it is to be done, and post a timing test comparing the two.

Easy.

I've lightened the load of Peters, and notice I'm even being a lot nicer in the post itself, and didn't even say anything about the Python losing its bite or talk about its cool but slimy scales.

Ok, on to the mathematics, as, why is this challenge significant?

Well, it turns out that as you optimize my prime counting function it approaches Meissel's Formula.

Now I know that, and have told Peters more than once that at the top end of the iterations it IS the equivalent of Meissel's Formula, but he just keeps babbling like he doesn't get it.

So a simple test is in order.

Let's see what Tim Peters—the supposed Python code guru—and his people say to this one.

Will they whine their way out, again?