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

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[12345678;87654321]$ , числа, у которых есть ровно $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$ из отрезка $[12345678;87654321]$ .

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


ans = 0  # Счётчик для ответа

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

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

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

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

Ответ: 6