Прототип на большие числа (Основная волна 2026)

Маски и делители

Условие задачи

Задание 25 (№31161).

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

Решение

def prime(n, p=2):
    for d in range(p, int(n ** .5) + 1):
        if n % d == 0:
            return [d] + prime(n // d, d)
    return [n]
k = 0
for n in range(8_117_600_757, 10 ** 100):
    if k == 5: break
    ds = prime(n)
    M = max(ds) - min(ds) if ds else 0
    if M and prime(M) == [M]:
        if str(M).count('1') >= 4:
            print(n, M)
            k += 1

# Функция раскладывает число на простые множители.
# Возвращает список простых множителей с учетом их кратности.
# Например:
# prime(20) -> [2, 2, 5]
# prime(45) -> [3, 3, 5]
def prime(n, p=2):

    # Перебираем возможные делители от p до √n.
    # Параметр p позволяет при рекурсивных вызовах
    # не начинать поиск делителей заново.
    for d in range(p, int(n ** .5) + 1):

        # Если найден делитель...
        if n % d == 0:

            # ...добавляем его в список и продолжаем
            # раскладывать оставшуюся часть числа.
            return [d] + prime(n // d, d)

    # Если делитель не найден, значит n — простое число.
    return [n]


# Счетчик найденных чисел.
k = 0

# Перебираем все натуральные числа,
# большие 8 117 600 756.
for n in range(8_117_600_757, 10 ** 100):

    # После нахождения пяти подходящих чисел
    # завершаем перебор.
    if k == 5:
        break

    # Получаем список простых множителей числа n.
    ds = prime(n)

    # Вычисляем M — разность максимального
    # и минимального простых делителей.
    # Если список пуст (в данной программе такого не бывает),
    # считаем M равным 0.
    M = max(ds) - min(ds) if ds else 0

    # Проверяем, что:
    # 1) M не равно 0;
    # 2) M является простым числом.
    # Простое число раскладывается только на само себя,
    # поэтому prime(M) == [M].
    if M and prime(M) == [M]:

        # Проверяем, что запись числа M
        # содержит не менее четырех цифр '1'.
        if str(M).count('1') >= 4:

            # Выводим найденное число и значение M.
            print(n, M)

            # Увеличиваем количество найденных ответов.
            k += 1

← К списку шпаргалок