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

Что проверяет номер

Перебор чисел тут большой, поэтому важно не делать лишнего. Если число заведомо кратно какому-то значению, идём по диапазону с этим шагом: цикл станет в десятки раз короче.

Два вида условий: (1) числа, подходящие под маску (123*4?5) и делящиеся на K, с выводом числа и частного; (2) числа с особыми делителями: количество делителей, произведение двух простых, M по простым делителям.

Простыми словами

Маска это шаблон для записи числа, как поиск по файлам. Знак ? значит «ровно одна любая цифра». Знак * значит «сколько угодно любых цифр, можно и ни одной». Под маску 1*3 подходят 13 и 1503, а под 1?3 подойдёт 123, но не подойдёт 13.

Делитель это число, на которое делится без остатка. Делители ходят парами: 1099 делится на 7, значит, и на 1099 // 7 = 157. Поэтому искать делители дальше корня незачем: всех больших мы получаем как пару к маленьким. Это сильно ускоряет код.

Простое число делится только на 1 и на себя. Разложить число на простые множители значит записать его как произведение простых: 1099 = 7 · 157.

Маски

Маска описывает запись числа: ? это ровно один символ, * любое их количество, в том числе ноль. Функция fnmatch делает такую проверку за нас, надо только привести число к строке.

from fnmatch import fnmatch
for x in range(1_000_008, 5_000_000, 17):          # шаг по кратности
    if fnmatch(str(x), '12*3?4') and x % 17 == 0:
        print(x, x // 17)

• * — любое количество любых символов (в том числе ни одного), ? — ровно один.
• Если число кратно K, перебираем с шагом K: в 17 раз быстрее.

# пиши решение здесь

Как читать маску

# пиши решение здесь

Множители: p, good, f

Делители идут парами: если нашли d, то x // d тоже делитель. Поэтому достаточно идти до корня из числа.

Для чисел вида «произведение двух простых, у каждого есть нужная цифра»:

def p(x):                                      # простое ли число
    return x > 1 and all(x % d != 0 for d in range(2, int(x ** 0.5) + 1))

def good(x):                                   # простое и ровно одна «5» в записи (в задаче подставь свою комбинацию)
    return str(x).count('5') == 1 and p(x)

def f(x):
    D = []
    for d in range(2, int(x ** 0.5) + 1):      # делители до корня
        if x % d == 0:
            if good(d) and good(x // d):       # и d, и пара к нему подходят
                D.append(d)
                D.append(x // d)
    return D

n = 0
for x in range(2000001, 10 ** 20):             # с числа, следующего за N
    D = f(x)
    if len(D) == 2:                            # ровно одна подходящая пара
        print(x, min(D))                       # если нужен наибольший, пиши max(D)
        n += 1
        if n == 5:
            break

Заменяешь '5' на комбинацию из условия и начало диапазона на N + 1. Если нужен наибольший множитель, пишешь max(D).

Разбор кода по функциям

• p(x) проверяет, простое ли число: нет ли делителей от 2 до корня. all(...) истинно, только если не делится ни на один.
• good(x) объединяет два условия: число простое и нужная комбинация цифр встречается в нём один раз.
• f(x) собирает подходящие множители в список D.

Посмотрим на примере с цифрой 7 вместо 5. Число 1099 делится на 7, и 1099 // 7 = 157. Оба простые, в каждом одна семёрка, поэтому D = [7, 157], и его длина 2. А число 1100 делится на 2, но 2 без семёрки, и пара не подойдёт. Ни один делитель не проходит проверку, и D останется пустым.

Почему проверяем len(D) == 2? Если число это произведение ровно двух простых, такая пара одна, и в D будет два числа. У числа с большим количеством множителей делители составные, и good их отсеет.

Почему до 10 ** 20? Это просто очень далёкая граница. Цикл всё равно остановится через break, когда найдёт пять чисел. Условие обычно просит первые пять после N.

# пиши решение здесь

Почему до корня

Возьмём 1099. Его делитель 7 найдётся быстро, а пара к нему 1099 // 7 = 157 получается сразу. Если бы у числа не было делителей до корня, их не было бы и после, потому что каждый большой делитель идёт в паре с маленьким.

# пиши решение здесь

Разложение на простые множители

Рекурсия отщепляет по одному наименьшему множителю, пока не останется простое число.

Для M по простым делителям:

def razl(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return [i] + razl(x // i)          # нашли делитель, раскладываем остаток
    return [x]                                  # простое число

razl(x) возвращает список простых множителей (с повторами). Из него берём наименьший min и наибольший max. Для простого числа в списке один элемент, делителей нет и M = 0.

n = 0
for x in range(1000000, 10 ** 20):
    r = razl(x)
    if len(r) == 1:                             # простое: M = 0, пропускаем
        continue
    s = set(r)
    m = max(s) - min(s)
    if str(m).count('1') >= 2 and p(m):          # условие из задачи
        print(x, m)
        n += 1
        if n == 5:
            break

# пиши решение здесь

Ловушки