Число n называется степенным,
если его можно представить в виде степени некоторого натурального числа,
возведённого хотя бы во вторую степень.
·
Например,
4 степенное число, так как 4 = 2².
·
Число
27 также степенное, так как 27 = 3³.
·
Однако
28 не является степенным числом.
Определите, какие из заданных чисел
являются степенными.
Вход. Первая строка содержит количество
чисел n (1 ≤ n ≤ 10). Во второй строке записаны n
целых чисел, каждое из которых больше 1 и меньше 10⁹.
Выход. Выведите n строк. В i-й
строке выведите “YES”,
если i-е число является степенным, и “NO” в противном случае.
Пример
входа |
Пример
выхода |
2 27 28 |
YES NO |
разложение
на множители
Пусть n – степенное
число. Тогда существуют такие натуральные i и k, что ik = n. Переберем
значение i = 2, 3, 4, …, . Для каждого значения i переберем его степени i, i2, i3, …, ik до тех пор пока
ik ≤ n.
Если найдутся
такие i и k, что ik = n, то число n является
степенным
Функция Degree определяет, является ли число n степенным.
int Degree(long long n)
{
long long i, j;
Перебираем i = 2, 3, 4, …, .
for (i = 2; i <= sqrt(n);
i++)
{
j = i * i;
Перебираем j = i, i2, i3, … .
while (j <= n)
{
Если существует такое k, что j = ik = n, то число n является
степенным.
if (j == n) return 1;
j *= i;
}
}
Число n не является степенным.
return 0;
}
Основная часть программы. Читаем количество тестов tests.
scanf("%d", &tests);
while (tests--)
{
Читаем входное число n.
scanf("%d", &n);
Определяем, является ли число n степенным. Выводим ответ.
if (Degree(n)) printf("YES\n");
else printf("NO\n");
}
import math
Функция is_power определяет, является ли число n степенным.
def is_power(n):
Перебираем i = 2, 3, 4, …, .
for i in range(2, int(math.sqrt(n)) + 1):
j = i * i
Перебираем j = i, i2, i3, … .
while j <= n:
Если существует такое k, что j = ik = n, то число n является
степенным.
if j == n:
return True
j *= i
Число n не является степенным.
return False
Основная часть программы. Читаем входные данные.
tests = int(input())
lst = list(map(int, input().split()))
for n in lst:
Определяем, является ли число n степенным. Выводим ответ.
print("YES" if is_power(n) else "NO")