Google Codejam 2011 Round 2 problem C

Problem

This is to find the number of "Prime powers p^m, m = 0 or m >= 2, thus excluding the primes" in http://oeis.org/A025475 , from 1 to n.

Here is the brief reason:

Max waiter calls: # prime and prime powers.

Min waiter calls: # primes.

So the spread of the two is the sequence as above.

I didn't expect that the number of elements when n=10^12 is still so small.