25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Пусть $M$ – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите программу, которая перебирает целые числа, большие $8,007,524,668$, в порядке возрастания и ищет среди них такие, для которых $M$ больше $110,000$, является простым числом и в своём написании содержит последовательность цифр $991$ ровно один раз.
В ответе запишите в первом столбце таблицы первые $5$ найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения $M$.
Например, для числа $49$ $M=14$; для числа $42$ $M=9$.
| | |
Так как $M$ должно быть простым числом больше $110,000$, оно нечётное. Если исходное число нечётное, его минимальный и максимальный простые делители также нечётные, поэтому их сумма будет чётной. Значит, подходящее число обязательно чётное.
Следовательно, минимальный простой делитель равен $2$, и $M=2+\text{максимальный простой делитель}$.
Будем перебирать только чётные числа и находить их максимальный простой делитель.
def prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
def max_div(n):
m = 0
while n % 2 == 0:
m = 2
n //= 2
d = 3
while d * d <= n:
while n % d == 0:
m = d
n //= d
d += 2
if n > 1:
m = max(m, n)
return m
n = 8007524670
k = 0
while k < 5:
d = max_div(n)
M = 2 + d
if M > 110000 and prime(M) and str(M).count('991') == 1:
print(n, M)
k += 1
n += 2
Функция max_div(n) находит максимальный простой делитель числа $n$.
Условие str(M).count(‘991’) == 1 проверяет, что последовательность цифр $991$ встречается в записи числа $M$ ровно один раз.
Программа выведет:
| Число | $M$ |
|---|---|
| $8007539144$ | $149911$ |
| $8007540788$ | $153991171$ |
| $8007540856$ | $142991803$ |
| $8007547448$ | $9910333$ |
| $8007550626$ | $150991$ |