Напишите программу, которая перебирает целые числа, большие 2 018 974 440, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит ровно один раз в своей записи последовательность цифр «43».
В ответе запишите в первом столбце таблице первые пять найденных чисел в порядке возрастания, во втором столбце — для каждого из них наименьший найденный множитель для каждого из них.
Количество строк в таблице для ответа избыточно.
Ответ:
##Приведём решение на языке Python.
def f(x):
for i in range(2, int(x**0.5)+1):
if x%i==0:
return [i]+f(x//i)
return [x]
count = 0
for x in range(2_018_974_441, 2_100_000_000):
d = f(x)
if len(d) == 2:
if str(d[0]).count('43') == 1 and str(d[1]).count('43') == 1:
print(x, min(d))
count += 1
if count == 5:
break
Примечание: программа выполняется продолжительное время.
В результате работы программа должна вывести следующее:
2018977769 27143
2018980091 9437
2018983349 643
2018997619 43
2019003907 4643
Приведём решение Юрия Красильникова на языке Python.
def prostmn(n): # Простые множители
mn = [] # Список множителей
d = 2 # Проверяемый множитель
while d * d <= n:
while n % d == 0: # Если делится, добавляем множитель
mn.append(d)
n //= d
d += 1 if d==2 else 2 # Пробуем 2, 3, 5, 7, 9... и т.д.
if n > 1: # n - оставшийся простой множитель
mn.append(n)
return mn
k,n = 0,2018974441
while k < 5:
d = prostmn(n)
if len(d) == 2 and all(str(x).count('43')==1 for x in d):
print(n, min(d))
k += 1
n += 1