25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Пусть $M$ – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите программу, которая перебирает целые числа, большие $8,007,494,154$, в порядке возрастания и ищет среди них такие, для которых $M$ больше $80,000$, является простым числом и в своём написании содержит последовательность цифр $567$ ($567$ – идущие подряд друг за другом в указанном порядке цифры $5$, $6$ и $7$) ровно один раз.
В ответе запишите в первом столбце таблицы первые $5$ найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения $M$.
Например, для числа $49$ $M=14$; для числа $42$ $M=9$.
| | |
Если исходное число нечётное, то его минимальный и максимальный простые делители нечётные. Их сумма $M$ будет чётной. Так как $M>80,000$ и должно быть простым, такие числа нам не подходят.
Значит, перебираем только чётные числа. Для них минимальный простой делитель равен $2$, поэтому $M=2+\text{максимальный простой делитель}$.
from math import isqrt
def prime(n):
if n < 2:
return False
for d in range(2, isqrt(n) + 1):
if n % d == 0:
return False
return True
def max_div(n):
m = 2
while n % 2 == 0:
n //= 2
d = 3
while d * d <= n:
if n % d == 0:
m = d
while n % d == 0:
n //= d
d += 2
if n > 1:
m = max(m, n)
return m
n = 8007494156
k = 0
while k < 5:
M = 2 + max_div(n)
if M > 80000 and str(M).count('567') == 1 and prime(M):
print(n, M)
k += 1
n += 2
Функция max_div(n) находит максимальный простой делитель числа $n$.
Условие str(M).count(‘567’) == 1 проверяет, что последовательность цифр $567$ встречается в записи $M$ ровно один раз.
Программа выведет:
| Число | $M$ |
|---|---|
| $8007495062$ | $615679$ |
| $8007495772$ | $5671033$ |
| $8007531302$ | $856789$ |
| $8007532410$ | $5679103$ |
| $8007559070$ | $1567039$ |