25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Напишите программу, которая перебирает целые числа, большие $2,626,695,891$, в порядке возрастания и ищет среди них числа, представимые в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи $67$ ($67$ – идущие подряд друг за другом в указанном порядке цифры $6$ и $7$).
В ответе в первом столбце таблицы запишите первые $5$ найденных чисел в порядке возрастания, а во втором столбце – для каждого из них соответствующий наименьший найденный множитель.
| | |
Если число представимо в виде произведения двух простых множителей $p\cdot q$, то достаточно найти его первый делитель $p$. Он будет простым. После этого проверяем, что $q=\dfrac{n}{p}$ тоже является простым числом и оба множителя содержат последовательность 67 ровно один раз.
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 f(n):
for d in range(2, isqrt(n) + 1):
if n % d == 0:
q = n // d
if (prime(q) and
str(d).count('67') == 1 and
str(q).count('67') == 1):
return d
return 0
return 0
n = 2626695892
k = 0
while k < 5:
d = f(n)
if d != 0:
print(n, d)
k += 1
n += 1
Функция f(n) находит первый делитель числа $n$. Если второй множитель тоже прост и в записи каждого множителя последовательность 67 встречается ровно один раз, функция возвращает меньший множитель.
Программа выведет:
| Число | Наименьший множитель |
|---|---|
| $2626696861$ | $6793$ |
| $2626700987$ | $1567$ |
| $2626704089$ | $167$ |
| $2626711691$ | $2267$ |
| $2626713493$ | $67$ |