Finding all composites in given limits

Question

I want to compute all composites

$x = a^{n}$

with

$n,a \in \Bbb{N}; \\ n,a>1 $

between two given limits.

Is there a simpler way, than brute-forcing?

Answer 1

Things are much easier if you are counting valid pairs of $a$ and $n$ rather than counting the actual values. (I.e. I'm assuming that you don't want to count duplicates even if the $a$ and $n$ are different). The strategy is still basically the same.

If you don't want to include duplicates, then it suffices to just use $n$ prime and then use inclusion exclusion principle to take care of duplicates. For a given $n$, say $n = 2$, if you compute the $n$th roots of your upper and lower bound then this will tell you how many squares you have in your range, without having to list them all. Then do $n = 3$, by taking cube roots of your upper and lower bound. If your range is not too large you won't have to do that many primes $n$. Then you need to subtract counts for all $n$ which are products of two of your primes, and then add counts for all $n$ that are products of three of your primes, and so forth (This is the inclusion-exclusion). If your range is numbers less than $2^k$ then the largest prime $n$ you'll need to consider is less than or equal to $k$. Also, you will probably only have to apply a few levels of inclusion-exclusion before your $n$ is too large to make $a^n$ fit in your range.