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

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

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

В данной задаче необходимо, чтобы у числа было ровно 5 различных делителей.

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

Тогда число имеет вид где – любое простое число.

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

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


# Нужно перебрать все числа вида x = p**4, где p - простое число
count = 0  # Количество подходящих чисел

# Находим максимально возможное p для отрезка
p_max = int(77_777_777 ** (1 / 4))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 11_111_111 <= p ** 4 <= 77_777_777:
            count += 1

print(count)  # Выводим ответ