Post History

Asymptotics of counting integers by prime signature

The prime counting function $\pi(n)$ which counts the number of primes up to $n$ is well-known, and it's also fairly well-known that using a well-optimised implementation of the [Meissel-Lehmer algorithm](https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm) it can be calculated in $\tilde O(n^{2/3})$ time. What about numbers of other forms?

To be specific, define the [*prime signature*](https://en.wikipedia.org/wiki/Prime_signature) $\textrm{sig}(x)$ as the multiset of the non-zero exponents in the prime factorisation of $x$, and define $\pi_s(n)$ as the number of integers up to $n$ with prime signature $s$ (so that the prime counting function is $\pi_{\\{1\\}}$). What can we say about how quickly we can calculate $\pi_s(n)$?