Is there a way to generate a counting function for prime powers - i.e. to create a similar function to
PrimePi, but including prime powers. The following will, of course, generate a list of these numbers:
Select[ Range, PrimePowerQ]
A naive approach would be this:
This function works well however it might be very inefficient for large
which is only a little bigger than
The latter is much more efficient since it uses advanced algorithms for counting primes which exploit sparse caching and sieving techniques ( in documentation pages see Some Notes on Internal Implementation, then J. C. Lagarias, V. S. Miller and A. M. Odlyzko "Computing
Therefore we proceed along a different way making use of
This might be done as well with:
Now we can find immediately:
For some limitations of
Here's a fancy memoized solution:
This is going to be conveniently fast for interactive use with "random" inputs. If you need to evaluate it for a complete
The idea is to store all previously calculated counts, and to compute any newly requested count relative to an already known (cached) one.
You can even pre-initialize this for a range of exponentially increasing values, e.g.
EDIT: I just saw Artes's answer, which is the best solution, as it exploits the specific problem. For general slow-to-evaluate brute force counting functions, I believe that my memoized approach is still valuable.
I can't complete with Artes's mathematical knowledge and approach, but simply as a point of reference, for formulating a brute-force approach it will be more memory efficient to use
Late again, but ...
In addition to
where n is the upper limit. However, these functions are both too slow.
The answer by @Artes uses
A cool method given by Riemann himself is to use
On my machine with