# Is it a power? P51271

Statement

thehtml

Write a program to tell if a natural number n is a non-trivial power, that is, if it can be expressed as xm, where both x and m are natural numbers, and m ≥ 2. For instance, some non-trivial powers are 243 = 35, 400 = 24 52 = (22 51)2, 216000 = 26 33 53 = (22 31 51)3, and 1866240000 = 212 36 54 = (26 33 52)2. By contrast, 3, 200 = 23 52, and 432000 = 27 33 53 are not non-trivial powers.

Input

Input consists of several cases, each with a natural number n between 2 and 106.

Output

Print every n followed by “yes” or “no”, depending on whether it is a non-trivial power.

Observation

You should not use the mathematical function pow() nor any alike function to solve this problem.

Hint

A possible solution uses a variant of the sieve of Eratosthenes to precompute a prime factor of each number before starting to read the input.

Public test cases
• Input

```243
400
216000
3
200
432000
1000000
999999
```

Output

```243 yes
400 yes
216000 yes
3 no
200 no
432000 no
1000000 yes
999999 no
```
• Information
Author