25.04 Основная теорема арифметики

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

Здесь – некоторое простое число, а – натуральный показатель степени. В таком случае число обязательно имеет делителей (каждое простое число можно брать от 0 до раз, где ).

В данной задаче необходимо, чтобы у числа было ровно 5 чётных делителей. Значит в разложении числа должно участвовать простое число 2.

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

Выпишем количество делителей числа:

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

Обозначим произведение всех за . Так как количество по условию должно быть равно 5, то . Так как число 5 – простое, то либо и , либо и .

В первом случае это число , так как означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех равно 5, а значит только 1 множитель должен быть равен 5 (так как 5 – простое число). Поэтому число будет иметь вид .

В общем случае это можно представить, как где – любое простое число (включая число 2, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида из отрезка .

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 = 2 * p**4, где p - простое число

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

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

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

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