Задание 25

Напишите программу, которая перебирает натуральные числа, большие 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» в записи. Потом перебираем их пары и берём пять самых маленьких произведений.