Задание 25

Напишите программу, которая перебирает целые числа, большие 8 996 452, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно две цифры 3.

В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого из чисел соответствующий им наибольший из найденных множителей.

Количество строк в таблице для ответа избыточно.

Решение

🔹 Шаг 1. Идея решения

📌

Перебираем числа больше 8996452 и ищем те, которые раскладываются в произведение 2 простых множителей, и каждый простой множитель содержит ровно 2 цифр(ы) 3 в записи.

Во втором столбце выводим наибольший из множителей.

🔹 Шаг 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(8_996_453, 10**10):
    factors = prime_factors(x)
    if len(factors) == 2 and all(str(p).count('3') == 2 for p in factors):
        print(x, max(factors))
        c += 1
        if c == 5:
            break

📌

Если длина списка множителей равна 2, число подходит — выводим его и наибольший множитель.

Останавливаемся после 5 найденных чисел.