ЕГЭ 25 25. Теория чисел в программировании Вариант 18.06.26 — разные города

0 XP

0 / 0

Напишите программу, которая перебирает целые числа, большие 1 103 285 717, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит ровно один раз в своей записи последовательность цифр «16».

В ответе для первых 5 найденных чисел запишите само число и наименьший из его простых множителей в соответствующие столбцы таблицы. Количество строк в таблице для ответа избыточно.

Решение

I способ (список простых)

def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True


primes = [x for x in range(100, 100000)
          if str(x).count("16") == 1 and is_prime(x)]


ans = []

for i, p in enumerate(primes):
    for q in primes[i:]:
        if p * q > 1_104_285_717:
            ans.append((p * q, p))

ans.sort()
print(*ans[:5], sep='\n')

Собираем простые числа с одним вхождением «16» в записи, перебираем пары и выводим пять наименьших произведений.

Переменная	Значение
нет переменных