Problem G
Mr. Azad and
His Son!!!!!
Input: standard input
Output: standard output
Time Limit: 4 seconds
There are a lot of Abul Kalam Azad in Bangladesh. But, why is he so
special? Not that he is my dad is the only reason. He can wonderfully do some
calculation. If anyone gives him any positive integer, he amazingly can say the
relative perfect number using the formula 2^(k-1)*(2^k-1) without using neither
calculator nor computer. Say, I have told him to find out the relative perfect
number of 2, he replies 6 which is a perfect number. But perfect is not
possible for all the integers. I have asked him the process, but he says that I
should find this thing out by myself how an integer is related to a perfect
number. Anyway, I have challenged him that it is very possible for me to do the
same calculation using a computer. Although I could not figure out how he can
do this, I know that the next ACM Online Programming Contest is near at hand
and World's top programmers are available to solve my very simple problem.
Now, you are to write a program for me to win over my dad, which will take input n, and determine the perfect number p.
An integer 1<n<=31 is given in each input
line. Input is terminated by a zero in a single line. This input should not be
processed. All the output numbers will fit in 64 bit signed integer.
Output
Output will be in the following format:
If perfect number is possible -
Perfect: p!
If perfect number is not possible, but given number is prime -
Given number is prime. But, NO perfect number is available.
If perfect number is not possible and given number is not prime -
Given number is NOT prime! NO perfect number is available.
2360
Perfect: 6!Perfect: 28!Given number is NOT prime! NO perfect number is available.
Tanzim Saqib