Напишите программу, которая перебирает натуральные числа, большие 1 104 285 717, являющиеся произведением ровно двух простых чисел, каждое из которых в записи содержит ровно одну цифру 16.
В ответе запишите первые 5 найденных чисел в порядке возрастания, слева от каждого числа запишите его наименьший делитель.
Решение
🔹 Шаг 1. Проверка простоты числа
def is_prime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
📌 Создаём функцию, которая проверяет, является ли число простым.
🔹 Шаг 2. Отбор простых с подстрокой «16»
primes = [x for x in range(100, 100000)
if str(x).count("16") == 1 and is_prime(x)]
📌 Собираем простые числа от 100 до 99999, в записи которых сочетание цифр 16 встречается ровно один раз.
🔹 Шаг 3. Перебор пар и отбор произведений
ans = []
for i, p in enumerate(primes):
for q in primes[i:]:
if p * q > 1_104_285_717:
ans.append((p * q, p))
📌 Перебираем пары простых чисел, находим их произведение и, если оно больше 1 104 285 717, сохраняем произведение и его наименьший простой делитель.
🔹 Шаг 4. Сортировка и вывод ответа
ans.sort()
print(*ans[:5], sep='
')
📌 Сортируем найденные пары по произведению и выводим первые 5 результатов.
