Write a program to tell if a natural number *n*
is a non-trivial power, that is,
if it can be expressed as *x*^{m}, where both *x* and *m* are natural numbers,
and *m* ≥ 2.
For instance, some non-trivial powers are 243 = 3^{5},
400 = 2^{4} 5^{2} = (2^{2} 5^{1})^{2},
216000 = 2^{6} 3^{3} 5^{3} = (2^{2} 3^{1} 5^{1})^{3},
and 1866240000 = 2^{12} 3^{6} 5^{4} = (2^{6} 3^{3} 5^{2})^{2}.
By contrast, 3,
200 = 2^{3} 5^{2},
and 432000 = 2^{7} 3^{3} 5^{3}
are not non-trivial powers.

**Input**

Input consists of several cases,
each with a natural number *n* between 2 and 10^{6}.

**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
- Jordi Cortadella
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++