Задание 25

(В. Лашин) Напишите программу, которая перебирает целые числа, большие 13 475 124, в порядке возрастания и ищет среди них числа, представленные в виде произведения 5 простых множителей, не обязательно различных, каждый из которых содержит в своей записи хотя бы одну цифру 5.

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

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

Решение

🔹 Шаг 1. Разложение на простые множители

def prime_factors(x):
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return [i] + prime_factors(x // i)
    return [x]

📌 Пишем рекурсивную функцию разложения числа на простые множители.

🔹 Шаг 2. Перебор чисел

c = 0

for x in range(13_475_124, 10**10):

📌 Задаём счётчик найденных ответов и перебираем числа больше 13 475 124.

🔹 Шаг 3. Проверка множителей

factors = prime_factors(x)
    if len(factors) == 5 and all('5' in str(p) for p in factors):

📌 Для каждого числа проверяем, что множителей ровно 5 и каждый содержит цифру 5.

🔹 Шаг 4. Вывод ответа

print(x, factors[4])
        c += 1
        if c == 5:
            exit()

📌 Выводим число и наибольший множитель и останавливаемся после 5 ответов.