Задача к ЕГЭ по информатике на тему «делители числа» №2

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[28916485;49716586]$ , числа, у которых есть ровно $5$ делителей, которые оканчиваются на $0$ или $5$ . Общее количество делителей числа может быть любым. В ответ запишите все найденные числа через пробел в порядке возрастания.

По основной теореме арифметики (ОТА) каждое натуральное число, большее 1, можно разложить на простые множители. То есть некоторое натуральное число $x$ можно разложить в следующий вид:

x = p1q1 ⋅p2q2 ⋅...⋅pnqn

Здесь $pi,i ∈ [1;n]$ – некоторое простое число, а $qi,i ∈ [1;n]$ – натуральный показатель степени. В таком случае число обязательно имеет $(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)$ делителей (каждое простое число можно брать от 0 до $qi$ раз, где $i ∈ [1;n]$ ).

В данной задаче необходимо, чтобы у числа было ровно 5 делителей, которые оканчиваются на 0 или 5. Тогда эти делители должны быть кратны числу 5, а значит в разложении числа должно участвовать простое число 5.

Пусть число имеет следующий вид:

k q1 qn x = 5 ⋅p1 ⋅...⋅pn

В таком случае количество делителей, кратных 5, будет равно $k ⋅(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1),$ обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 5, то либо $k = 5$ и $m = 1$ , либо $k = 1$ и $m = 5$ . Для $m = 5$ аналогично будет только 1 множитель, а значит только 1 простое число в степени с показателем 4. В общем случае это можно представить, как $1 4 5 ⋅p ,$ где $p$ – любое простое число (в том числе 5, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p4 ⋅5$ из отрезка $[28916485;49716586]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True

# Нужно перебрать все числа вида x = 5 * p**4, где p - простое число

l = 28916485  # Левая граница отрезка
# Делим на 5, а затем извлекаем корень 4 степени,
# чтобы получить первое возможное p
l = int((l / 5) ** (1 / 4))

# Аналогично с правой границей отрезка
r = 49716586
r = int((r / 5) ** (1 / 4))

# Перебираем числа от l до r включительно
ans = []  # Список чисел для ответа
for p in range(l, r + 1):
    if is_prime(p):  # Если число p - простое
        # Проверяем, что итоговое число будет принадлежать отрезку
        if 28916485 <= 5 * p ** 4 <= 49716586:
            ans.append(5 * p ** 4)

print(*ans)  # Выводим элементы списка через пробел

Ответ: 39452405