Напишите программу, которая перебирает целые числа, большие 2 626 695 891, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи 67 (67 — идущие подряд друг за другом в указанном порядке цифры 6 и 7).
В ответе в первом столбце таблицы запишите первые 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. Разложение на простые множители
def prime_factors(x):
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return [i] + prime_factors(x // i)
return [x]
📌 Пишем функцию разложения числа на простые множители.
🔹 Шаг 3. Перебор чисел и проверка множителей
c = 0
for x in range(2_626_695_892, 10**10):
factors = prime_factors(x)
if len(factors) == 2 and str(factors[0]).count('67') == 1 and str(factors[1]).count('67') == 1:
📌 Перебираем числа больше 2 626 695 891, раскладываем на множители и проверяем, что множителей ровно 2, а каждый содержит 67 ровно один раз.
🔹 Шаг 4. Вывод ответа
print(x, factors[0])
c += 1
if c == 5:
break
📌 Выводим число и меньший множитель и останавливаемся после 5 ответов.
