Задание 25

Пусть М - разность максимального и минимального простых натуральных делителей целого числа, не считая самого числа.

Если таких делителей у числа нет, то значение М считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 8 117 600 756, в порядке возрастания и ищет среди них такие, для которых М является простым числом и в своей записи содержит не менее четырёх цифр 1.

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

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

Решение

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

📌

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

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

🔹 Шаг 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_117_600_757, 10**10):
    factors = prime_factors(x)
    if len(factors) <= 1:
        continue
    M = max(factors) - min(factors)
    if is_prime(M) and str(M).count('1') >= 4:
        print(x, M)
        c += 1
        if c == 5:
            break

📌

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

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