Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа.
Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 7 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 63 и кратно общему количеству различных простых делителей числа.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.
Например, для числа 14 М = 2 + 7 = 9.
Количество строк в таблице для ответа избыточно.
Решение
🔹 Шаг 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(7_800_001, 10**10):
📌 Задаём счётчик найденных ответов и перебираем числа больше 7 800 000.
🔹 Шаг 3. Проверка условия для M
factors = set(prime_factors(x))
M = max(factors) + min(factors)
if M % 100 == 63 and M % len(factors) == 0:
📌 Для каждого числа считаем M как сумму минимального и максимального простого делителя и проверяем, что M оканчивается на 63 и делится на количество различных делителей.
🔹 Шаг 4. Вывод ответа
print(x, M)
c += 1
if c == 5:
exit()
📌 Выводим число и значение M и останавливаемся после 5 найденных пар.
