Задание 25 (ЕГЭ по информатике) поиск чисел, которые являются степенью простого числа с натуральным показателем степени, большим 1

 Задача (№ 25, ЕГЭ по информатике)

Напишите программу, которая перебирает целые числа, большие 700 000, в порядке возрастания и ищет среди них такие, которые являются степенью простого числа с натуральным показателем степени, большим 1.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого из чисел соответствующие им простое число.

Например, число 27 = 3³

Количество строк в таблице для ответа избыточно.

Алгоритм решения

1. Перебираем числа, начиная с 700 001.

2. Для каждого числа находим его разложение на простые множители с учётом кратности (функция f(n)).

3. Проверяем два условия:

   • Количество множителей в разложении больше 1 (показатель степени > 1).

   • Все множители одинаковые (число является степенью одного простого числа).

4. Как только находим 5 таких чисел, завершаем перебор.

Программа решения задачи на языке Python

def f(n):
    d = []
    for k in range(2, int(n**0.5) + 1):
        while n % k == 0:
            d.append(k)
            n //= k
    if n > 1:
        d.append(n)
    return d

k = 0
x = 700001
while k != 5:
    y = f(x)
    y1 = set(y)
    if len(y) > 1 and len(y1) == 1:
        print(x, y[0])
        k += 1
    x += 1

Пояснения

• Функция f(n) возвращает список простых делителей числа $n$ (например, для числа 72 → [2, 2, 2, 3, 3]).

• y1 = set(y) оставляет только уникальные делители. Если все делители одинаковые, длина множества будет равна 1.

• Условие len(y) > 1 гарантирует, что показатель степени больше 1.

Результат выполнения программы

703921 839

704969 89

707281 29

727609 853

734449 857