A positive integer $n$ is called a perfect power if and only if there exist two positive integers $p,q$, both are greater than 1, such that $n=p^q$. For example $8=2^3, 36=6^2$ are perfect powers, but $20=2^2*5, 11=11^1$ are not.
Let $A=\{1,2,\dots,1000\}$. How many elements of $A$ is a perfect power?
I hope there exist a beautiful way to solve this, perhaps without calculating the number of primes untill 1000 or considering all the cases. Is there a formula? Thanks in advance!