posted by Nathan on .
How many integers are NOT perfect powers between 1 and 1000?
It might be easier to count how many are powers and subtract that number from 1000. To do this you should first find the highest power of 2 less than 1000, then you'll know how high of powers you have to count. You can check that
29 < 1000 < 210
so you'll need to check up to 9th powers.
For squares find the last square less than 1000 (this is 31^2)
then the last cube less than 1000
Skip fourth powers because they're also squares.
then the last fifth powers less than 1000
Skip sixth powers because they're also squares.
then the last ninth powers less than 1000
Be sure that you don't double count, because fourth, sixth eigth and tenth powers are also squares, so you really only need to look at prime powers.
You want the first square, cube, fifth, seventh and ninth powers such that they don't exceed 1000, but the next integer does, like 31 and 32 above.