Is it a power? P51271


Statement
 

pdf   zip

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