Напишите программу, которая перебирает натуральные числа, большие 1 104 285 717, являющиеся произведением ровно двух простых чисел, каждое из которых в записи содержит ровно одну цифру 16.
В ответе запишите первые 5 найденных чисел в порядке возрастания, слева от каждого числа запишите его наименьший делитель.
Решение
Список простых
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» в записи. Потом перебираем их пары и берём пять самых маленьких произведений.
