25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Напишите программу, которая перебирает целые числа, большие $2,018,974,447$, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи $43$ ($43$ – идущие подряд друг за другом в указанном порядке цифры $4$ и $3$).
В ответе в первом столбце таблицы запишите первые $5$ найденных чисел в порядке возрастания, а во втором столбце – для каждого из них соответствующий наименьший найденный множитель.
| | |
Если число имеет вид $n=p\cdot q$, где $p$ и $q$ — простые числа, то достаточно найти наименьший делитель $p$. После этого проверяем, что второй множитель $q=\dfrac{n}{p}$ тоже является простым числом и каждый из множителей содержит 43 ровно один раз.
from math import isqrt
def prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
for d in range(3, isqrt(n) + 1, 2):
if n % d == 0:
return False
return True
def f(n):
if n % 2 == 0:
p = 2
else:
p = 0
for d in range(3, isqrt(n) + 1, 2):
if n % d == 0:
p = d
break
if p == 0:
return 0
q = n // p
if (str(p).count('43') == 1 and
str(q).count('43') == 1 and
prime(q)):
return p
return 0
n = 2018974448
k = 0
while k < 5:
d = f(n)
if d != 0:
print(n, d)
k += 1
n += 1
Функция f(n) находит наименьший простой множитель числа $n$. Затем проверяется, что второй множитель тоже простой и последовательность 43 встречается в каждом множителе ровно один раз.
Программа выведет:
| Число | Наименьший множитель |
|---|---|
| $2018977769$ | $27143$ |
| $2018980091$ | $9437$ |
| $2018983349$ | $643$ |
| $2018997619$ | $43$ |
| $2019003907$ | $4643$ |