Count the Perfect Powers

A perfect power is a number that can be written as a ** b with whole numbers a >= 1 and b >= 2. They start 1, 4, 8, 9, 16, 25, 27, 32, 36, ... Some numbers are powers in more than one way (64 is 8 2, 4 3 and 2 ** 6), but each number counts once.

Write count_perfect_powers(n) that returns how many numbers from 1 to n are perfect powers.

Examples

count_perfect_powers(10)     # returns 4
count_perfect_powers(100)    # returns 13
count_perfect_powers(1)      # returns 1

Up to 10 they are 1, 4, 8 and 9.

Constraints

• 1 <= n <= 10^18
• Floating-point roots are not exact at this size: int((10 ** 18 - 1) ** 0.5) is 1000000000, one too many. Check every root you compute with whole-number arithmetic.