Делители и маски чисел

В задаче № 25 нужно перебрать натуральные числа из заданного диапазона и найти те, которые подходят по свойству делимости и совпадают с маской. Маску записывают со специальными символами:

• ? — ровно одна произвольная цифра;
• * — любая последовательность цифр, в том числе пустая.

Например, маске 1?5 соответствуют числа 105, 115, 125, …, 195, а маске 1*7 — 17, 107, 147, 1237 и многие другие.

Проверка маски

В Python удобно пользоваться модулем fnmatch: он понимает те же символы ? и * и работает со строками.

from fnmatch import fnmatch

print([n for n in range(100, 200) if fnmatch(str(n), '1?5')])
# [105, 115, 125, 135, 145, 155, 165, 175, 185, 195]

print([n for n in range(1, 400) if fnmatch(str(n), '1*7') and n % 7 == 0][:6])
# [147]

Число нужно превращать в строку: маска применяется к записи числа. Если в условии маска содержит *, у числа может быть разная длина, поэтому диапазон перебора определяйте по условию, а не «на глаз».

Поиск всех делителей

Делители числа n идут парами (d, n // d), и меньший делитель из пары не превосходит √n. Поэтому достаточно перебрать d до √n:

def divisors(n):
    found = set()
    d = 1
    while d * d <= n:
        if n % d == 0:
            found.add(d)
            found.add(n // d)
        d += 1
    return sorted(found)

print(divisors(36))   # [1, 2, 3, 4, 6, 9, 12, 18, 36]
print(divisors(97))   # [1, 97]

Квадрат числа (36 = 6·6) даёт одинаковые делители в паре, и множество set убирает дубль.

Простое число — число больше 1 с ровно двумя делителями, как 97. Число с нужным количеством делителей отбирают так: len(divisors(n)) == k. Для больших диапазонов используйте решето Эратосфена и не вызывайте divisors для каждого числа без необходимости.

Типичная постановка

Часто просят вывести первые несколько чисел из диапазона, которые подходят под маску, делятся на заданное число без остатка, и для каждого — найденный по условию делитель (например, наибольший или частное). Каркас решения всегда одинаковый:

from fnmatch import fnmatch

count = 0
for n in range(1, 10**7):
    if fnmatch(str(n), '1?5*') and n % 13 == 0:
        print(n, n // 13)
        count += 1
        if count == 5:
            break

Диапазон и маска здесь только пример: подставьте значения из своей задачи и проверьте программу на маленьком диапазоне, где ответ можно найти вручную.

Типичные ошибки

• Применяют маску к числу, а не к его строковой записи.
• Забывают, что * может соответствовать пустой строке: число 17 подходит под маску 1*7.
• Считают делители до n, а не до √n: программа успевает за секунды, а не за часы.
• Забывают, что для числа 1 и для квадратов количество делителей считается иначе, чем «пары».
• Выводят числа не в том порядке, который требует условие: проверьте сортировку.