Control C301A P57404


Statement
 

pdf   zip

thehtml

A natural number n > 0 is called powerful if, for each prime divisor p of n, p2 is also divisor of n. For example, 55125 = 3·3·5·5·5·7·7 is a powerful number, because every prime factor appears, at least, twice.

Your task is to write a program that reads a sequence of numbers m and, for each one, prints all the powerful numbers between ‍1 and ‍m.

Input

The input is a sequence of natural numbers m > 0.

Output

For each m of the input, print a line with all the powerful numbers between 1 and m, separated by commas and in increasing order.

Observation

Your program must implement and use the function

bool is_powerful(int n);

that, given an integer strictly positive |n|, indicates if is powerful or is not

Public test cases
  • Input

    27
    28
    26
    1
    3
    4
    270
    

    Output

    1,4,8,9,16,25,27
    1,4,8,9,16,25,27
    1,4,8,9,16,25
    1
    1
    1,4
    1,4,8,9,16,25,27,32,36,49,64,72,81,100,108,121,125,128,144,169,196,200,216,225,243,256
    
  • Information
    Author
    Professorat de P1
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++