Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа.
Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 7 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 63 и кратно общему количеству различных простых делителей числа.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.
Например, для числа 14 М = 2 + 7 = 9.
Количество строк в таблице для ответа избыточно.
Решение
🔹 Шаг 1. Идея решения
📌
Для каждого числа больше 7800000 находим все простые делители (кроме самого числа), считаем M = минимальный + максимальный и проверяем условия задачи.
🔹 Шаг 2. Проверка простоты числа
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
📌 Вспомогательная функция is_prime(n) нужна, чтобы отличать простые делители от составных.
🔹 Шаг 3. Перебор чисел и проверка условия для M
c = 0
for x in range(7_800_001, 10**10):
primes = []
for d in range(2, int(x ** 0.5) + 1):
if x % d == 0:
if is_prime(d):
primes.append(d)
if d != x // d and is_prime(x // d):
primes.append(x // d)
if not primes:
M = 0
else:
M = min(primes) + max(primes)
k = len(set(primes))
if M % 100 == 63 and k > 0 and M % k == 0:
print(x, M)
c += 1
if c == 5:
break
📌 Алгоритм:
собираем все простые делители числа;
если делителей нет, M = 0;
иначе M = min + max по простым делителям;
проверяем, что M оканчивается на 63 и делится на количество различных простых делителей;
выводим первые 5 подходящих пар.