2328. Degree numbers

A number n is called a power number if it can be represented as a power of some positive integer raised to at least the second power.

· For example, 4 is a power number because 4 = 2².

· The number 27 is also a power number because 27 = 3³.

· However, 28 is not a power number.

Determine which of the given numbers are power numbers.

Input. The first line contains the number of integers n (1 ≤ n ≤ 10).
The second line contains n integers, each greater than 1 and less than 10⁹.

Output. Print n lines. On the i-th line, print “YES” if the i-th number is a power number, and “NO” otherwise.

Sample input	Sample output
2 27 28	YES NO

SOLUTION

factorization

Algorithm analysis

Let n be a power number. Then there exist positive integers i and k such that i^k = n. Iterate over values of i = 2, 3, 4, … . For each i, compute its powers: i, i², i³, …, i^k until i^k ≤ n.

If we find such i and k that i^k = n, then n is a power number.

Algorithm implementation

The function Degree determines whether the number n is a power number.

int Degree(long long n)

{

long long i, j;

Iterate over i = 2, 3, 4, …, .

for (i = 2; i <= sqrt(n); i++)

{

j = i * i;

Iterate over j = i, i², i³, … .

while (j <= n)

{

If there exists a k such that j = i^k = n, then the number n is a power number.

if (j == n) return 1;

j *= i;

}

}

The number n is not a power number.

return 0;

}

The main part of the program. Read the number of test cases tests.

scanf("%d", &tests);

while (tests--)

{

Read the input number n.

scanf("%d", &n);

Determine if the number n is a power number. Print the result.

if (Degree(n)) printf("YES\n");

else printf("NO\n");

}

Python implementation

import math

The function is_power determines whether the number n is a power number.

def is_power(n):

Iterate over i = 2, 3, 4, …, .

for i in range(2, int(math.sqrt(n)) + 1):

j = i * i

Iterate over j = i, i², i³, … .

while j <= n:

If there exists a k such that j = i^k = n, then the number n is a power number.

if j == n:

return True

j *= i

The number n is not a power number.

return False

The main part of the program. Read the input data.

tests = int(input())

lst = list(map(int, input().split()))

for n in lst:

Determine if the number n is a power number. Print the result.

print("YES" if is_power(n) else "NO")