Назовём маску числа последовательность цифр, в которой некоторые цифры заменены на символ «*». Например, маска 12**4* соответствует числам 120040, 125874 и другим.
Напишите программу, которая перебирает натуральные числа, большие 1 104 285 717, являющиеся произведением ровно двух простых чисел, каждое из которых в записи содержит ровно одну цифру 16. В ответе запишите первые 5 найденных чисел в порядке возрастания, слева от каждого числа запишите его наименьший делитель.
Решение
🔹 Шаг 1. Идея решения
📌
Перебираем числа больше 1104285717 и ищем те, которые раскладываются в произведение 2 простых множителей.
Во втором столбце выводим наибольший из множителей.
🔹 Шаг 2. Проверка простоты
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
📌 Функция is_prime используется при разложении на множители.
🔹 Шаг 3. Разложение на простые множители
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1 if d == 2 else 2
if n > 1:
factors.append(n)
return factors
📌 Функция prime_factors возвращает список простых множителей с учётом кратности (например, 12 = 2·2·3 → три множителя).
🔹 Шаг 4. Перебор чисел и вывод ответа
c = 0
for x in range(1_104_285_718, 10**10):
factors = prime_factors(x)
if len(factors) == 2:
print(x, max(factors))
c += 1
if c == 5:
break
📌
Если длина списка множителей равна 2, число подходит — выводим его и наибольший множитель.
Останавливаемся после 5 найденных чисел.
