Алгоритмы и программирование · 1 балл

Натуральные числа

Цифры и делители

Найти числа с заданными свойствами цифр, делителей, простоты или маски.

Алгоритмы числа и делители

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

Обработка натуральных чисел: делители, простые числа, цифры, маски и решето Эратосфена.

Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы

Теория

Что нужно знать

Задание 25 — это программирование, а не ручной счёт. Нужно перебрать числа на отрезке или кандидатов по маске, разложить число на множители, посчитать делители и выбрать те, что удовлетворяют условию. В базе Kompege по теме 1 075 задач, 124 решения (119 программных и 5 текстовых) и 241 видеоразбор (144 YouTube, 63 VK, 34 Rutube). Около 490 формулировок связаны с делителями, 462 — с масками, а 102 задачи совмещают оба условия.

Минимум для задания 25

делитель, кратное, остаток и целочисленное деление
поиск делителей перебором до √N
простые и составные числа, единица
разложение на простые множители
количество и сумма делителей через степени простых
чётные, нечётные и нетривиальные делители
пары делителей d и N/d
наибольший, наименьший и k-й по величине делитель
полный квадрат и нечётное число делителей
сумма и произведение делителей, их чётность
цифры числа, сумма цифр, палиндром, последняя цифра
маски «?» и «*», функция fnmatch
перебор кратных и генерация кандидатов по маске
решето Эратосфена и проверка простоты
оценка сложности и ранний выход из цикла
формат ответа: пары, порядок, частное

Число и его делители

Делитель натурального числа N — такое натуральное d, при котором N делится на d без остатка. У каждого делителя есть пара N/d, поэтому все делители удобно искать до √N: если d ≤ √N делит N, то N/d — второй делитель пары. Единица и само N тоже являются делителями, но во многих формулировках их просят не учитывать.

Если d делит N, то и N // d делит N: делители идут парами.
При переборе d от 2 до isqrt(N) добавляйте оба числа: d и N // d.
Если d = N // d, делитель один: это полный квадрат, не добавляйте его дважды.
«Нетривиальные» делители — все, кроме 1 и N; «собственные» — все, кроме N.
Простые числа имеют ровно два делителя: 1 и само число.
Ноль не является делителем натурального числа.

d | N ⇔ N % d == 0N = d · (N // d)d ≤ √N ⇔ N // d ≥ √N

Простые числа и разложение

Простое число делится только на 1 и на себя. Единица не является ни простой, ни составной. Любое N > 1 единственным образом раскладывается на простые множители: N = p1^a1 · p2^a2 · … · pk^ak. Это разложение — ключ к задачам, где делители нельзя перечислить вручную.

Проверка простоты — перебор d от 2 до isqrt(N); найденный делитель означает составное число.
2 — единственное чётное простое; после проверки 2 можно идти только по нечётным d.
Для разложения делите N на p, пока оно делится; так в словаре останутся степени.
«Различные простые делители» — ключи разложения; с кратностью — с повторами.
Для сотен тысяч чисел решето Эратосфена быстрее проверки каждого числа отдельно.
Оставшееся число больше 1 после trial division — простое, его тоже нужно добавить.

N = p1^a1 · p2^a2 · … · pk^akпростое число: ровно 2 делителя1 — не простое и не составное

Сколько делителей у числа

Если N = p1^a1 · p2^a2 · … · pk^ak, то количество всех натуральных делителей τ(N) = (a1+1)(a2+1)…(ak+1). Множитель (ai+1) — число способов выбрать степень pi от 0 до ai. Формула незаменима, когда N огромно или когда известно только разложение.

τ(360) = τ(2^3 · 3^2 · 5) = 4 · 3 · 2 = 24.
Количество нетривиальных делителей = τ(N) − 2.
τ(N) нечётно тогда и только тогда, когда N — полный квадрат.
Если N = 2^a · m и m нечётно, чётных делителей ровно a · τ(m), нечётных — τ(m).
Ровно три чётных делителя, считая само N: N = 8 или N = 2p².
Если N не считать, ровно три чётных делителя дают N = 16, 4p, 2p³ или 2pq (p и q — различные нечётные простые).
Ровно пять различных нечётных делителей: нечётная часть N имеет вид p⁴.

τ(N) = (a1+1)(a2+1)…(ak+1)чётных делителей: a · τ(m), где N = 2^a · mнечётных делителей: τ(m)τ(N) нечётно ⇔ N — полный квадрат

Сумма делителей

Сумма всех делителей σ(N) также выражается через разложение: σ(N) = ∏ (p^(a+1) − 1)/(p − 1). Чтобы получить сумму без 1 и самого N, вычтите 1 и N. Для суммы только простых делителей используйте ключи разложения, а не все делители.

σ(360) = 15 · 13 · 6 = 1170; сумма без 1 и 360 равна 809.
Сумма простых делителей без кратности — сумма ключей разложения.
Сумма простых делителей с кратностью — сумма p · a по всем p.
Если N = 2^a · m, сумма чётных делителей равна (2 + 4 + … + 2^a) · σ(m).
Сумма нечётных делителей — это σ(m), где m — нечётная часть N.
σ(N) нечётна тогда и только тогда, когда N — квадрат или удвоенный квадрат.

σ(N) = ∏ (p^(a+1) − 1)/(p − 1)сумма без 1 и N: σ(N) − 1 − Nσ(N) нечётна ⇔ N = t² или N = 2t²

Парные делители и позиции

Делители идут парами d и N/d. Поэтому наименьший нетривиальный делитель — первый найденный d > 1, а наибольший собственный делитель — N / d_min для составного N. Пятый по величине делитель — это N, делённое на пятый по возрастанию нетривиальный делитель.

Наибольший делитель, не равный N, равен N // d_min, где d_min — наименьший простой делитель.
k-й по величине нетривиальный делитель = N // (k-й по возрастанию нетривиальный).
Минимальный и максимальный нетривиальные делители: d_min и N // d_min.
Сумма пары равна d + N/d; пара ближе к √N, когда d ближе к корню.
«Пятый по величине» проще искать, собрав и отсортировав делители; при огромном N — через пять наименьших.
Для простого числа нетривиальных делителей нет, поэтому M(N) = 0 по условию.

d · (N // d) = Nmax_proper = N // min_divisor_>1k-й_max = N // (k-й_min)

Чётность и особые свойства

Многие условия читаются через строение числа, а не через полный перебор. Чётность количества делителей, нечётность суммы, произведение делителей и точное число делителей — всё это признаки, которые проверяются по разложению.

Все делители нечётны тогда и только тогда, когда N нечётно.
Сумма всех делителей нечётна тогда и только тогда, когда N — квадрат или удвоенный квадрат.
Произведение всех делителей равно N^(τ(N)/2); для полного квадрата это (√N)^τ(N).
Если сумма и произведение делителей нечётны, N — нечётный квадрат.
Ровно 4 делителя: N = p³ или N = p · q (p ≠ q).
Ровно 6 делителей: N = p⁵ или N = p² · q.
Ровно 9 делителей: N = p⁸ или N = p² · q².

τ = 4: p³ или p · qτ = 6: p⁵ или p² · qτ = 9: p⁸ или p² · q²произведение делителей = N^(τ/2)

Цифры, окончания и остатки

В задании 25 часто комбинируют делители с десятичной записью: делитель оканчивается на 7, сумма цифр кратна 14, число является палиндромом. Сначала выделите дешёвое цифровое условие, затем проверяйте делители.

Последняя цифра: n % 10; две последние: n % 100; три последние: n % 1000.
Сумма цифр: sum(map(int, str(n))); произведение считайте отдельно, ноль — особый случай.
Палиндром: s == s[::-1].
«Делитель оканчивается на d» — это d % 10 == digit, а не N % 10.
«Делитель двузначный» — 10 ≤ d ≤ 99; «трёхзначный» — 100 ≤ d ≤ 999.
Остаток от деления суммы делителей: сначала сумма, затем % m.

last = n % 10digits = [int(c) for c in str(n)]palindrome: s == s[::-1]

Маски «?» и «*»

Маска — это строка из цифр и символов «?» и «*». «?» заменяет ровно одну цифру, «*» — любую последовательность цифр, в том числе пустую. В Python маску проверяет fnmatch.fnmatchcase. Маска задаёт не число, а его десятичную запись, поэтому важна длина и то, что у числа нет ведущих нулей.

fnmatchcase(str(x), '12*4?5') истинно, если вся запись x подходит под маску.
«*» может соответствовать пустой строке; «?» — ровно один символ.
Если маска начинается с «?», первая цифра числа всё равно не может быть нулём.
Для делимости на m перебирайте не все числа, а кратные: range(m, limit + 1, m).
Маска без «*» задаёт точную длину; с «*» длина переменная.
fnmatch трактует квадратные скобки как класс символов; в экзаменационных масках их нет.

from fnmatch import fnmatchcaserange(m, limit + 1, m)«?» = 1 цифра, «*» = 0 или больше цифр

Стратегия и сложность

Главная ошибка — перебирать слишком широкий диапазон с полной проверкой делителей. Сначала оцените количество чисел и стоимость проверки. Если чисел несколько тысяч, прямой перебор с √N обычно успевает; если чисел 10⁵ и больше, даже проверка до корня может занять минуты — ищите строение числа, маску или кратные.

Стоимость прямой проверки: длина диапазона × √N. Для 10⁵ чисел около 10⁹ операций — уже медленно.
Для 10⁷–10⁸ чисел используйте решето или проверяйте только кратных и кандидатов.
math.isqrt(N) точнее и быстрее, чем int(N ** 0.5) на больших числах.
Проверяйте дешёвые условия (маска, последняя цифра, чётность) раньше перебора делителей.
При «первых N» ставьте break сразу после N-го найденного; при «последних N» идите вниз.
Если ответ не находится, увеличивайте лимит постепенно и проверяйте границы.

O(len · √N) — прямой переборрешето: O(n log log n), память O(n)isqrt(N) вместо N ** 0.5

Формат ответа

В задании 25 ответ — не одно число, а таблица пар или несколько значений. Формулировка всегда уточняет порядок: по возрастанию числа, по возрастанию делителей, сначала N, затем делитель или наоборот. Перечитайте её перед записью.

«Запишите само число и …» — сначала N; «справа от числа» — N, затем значение.
«Два наибольших делителя в порядке возрастания» — меньший, затем больший.
«В порядке убывания» — начинайте с большего и не сортируйте по возрастанию по привычке.
«Частное от деления» — это x // d, а не сам делитель.
«Количество подходящих чисел» — одно число, а не список.
Границы: [a; b] включает b; «больше a» начинается с a+1; «меньше b» заканчивается b−1.
Лишние строки таблицы в бланке не заполняйте.

[a; b] → range(a, b + 1)x > a → range(a + 1, …)x < b → range(…, b)

Разбор примера

Учебный пример: ровно четыре делителя

На отрезке [110; 120] найдите числа, у которых ровно четыре различных натуральных делителя. Для каждого найденного числа выведите два наибольших делителя, не равных самому числу, в порядке возрастания.

Числа отрезка [110; 120] с четырьмя делителями
N	Все делители	Два наибольших делителя без N
111	1, 3, 37, 111	3, 37
115	1, 5, 23, 115	5, 23
118	1, 2, 59, 118	2, 59
119	1, 7, 17, 119	7, 17

Для каждого N от 110 до 120 заводим множество делителей и добавляем 1 и N.
Перебираем d от 2 до isqrt(N); если d делит N, добавляем d и N // d.
Сортируем делители: у 111 получаем 1, 3, 37, 111.
Условию len(делителей) == 4 удовлетворяют 111, 115, 118 и 119.
Для каждого берём делители с индексами 1 и 2 — два наибольших, не считая N.
Выводим пары в порядке возрастания N и делителей: 3 37, 5 23, 2 59, 7 17.

Ответ3 37; 5 23; 2 59; 7 17.

Способы решения

Выберите метод под формулировку

Методы собраны по решениям задания 25 из базы Kompege. Начните с того, что именно нужно найти в условии.

ровно k делителей, сумма, минимум и максимум

Делители до корня: базовый перебор

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

Запишите границы отрезка и проверьте, включён ли правый конец.
Для каждого N заведите множество делителей и добавьте 1 и N.
Переберите d от 2 до isqrt(N); если d делит N, добавьте d и N // d.
Отсортируйте делители и примените условие задачи.
Напечатайте N и требуемые делители в указанном порядке.

Множество убирает повтор, когда d = N // d (полный квадрат).
Если нужны только количество и сумма, список можно не хранить, но с множеством проще не ошибиться.
«Ровно k делителей» — это len(ds) == k; «ровно k нетривиальных» — len(ds) - 2 == k.
Два наибольших делителя — ds[-1] и ds[-2]; если N исключён, берите ds[-2] и ds[-3] и выводите их по возрастанию.
Перебор до isqrt(N), а не до N // 2 — главное ускорение.

Пример

На отрезке [110; 120] найдите числа с ровно четырьмя делителями и выведите два наибольших делителя, не равных N, в порядке возрастания.

from math import isqrt

def divisors(n):
    ds = {1, n}
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            ds.add(d)
            ds.add(n // d)
    return sorted(ds)

for n in range(110, 121):
    ds = divisors(n)
    if len(ds) == 4:
        print(n, ds[1], ds[2])

Ответ111 3 37; 115 5 23; 118 2 59; 119 7 17.

По решениям № 892, 893, 900, 6148.

простые числа и простые делители

Простые числа: проверка и решето

Когда использовать: Нужно найти простые числа на отрезке, разложить число или получить его простые делители — с кратностью или без.

Для одного числа проверяйте d от 2 до isqrt(N); для 2 и чётных случаев сделайте отдельные ветки.
Для разложения делите N на найденный p, пока оно делится, и запоминайте степень.
Для большого отрезка постройте решето Эратосфена и проверяйте простоту по массиву.
Для суммы или количества простых после решета постройте префиксные суммы.
Не забудьте добавить остаток N > 1 в разложение.

1 не является простым; 2 — простое и единственное чётное простое.
Проверять делители достаточно до isqrt(N).
«Простые делители» — не все делители: у 12 это 2 и 3.
Для различных простых делителей делите N на p полностью; для кратности сохраняйте показатель.
Решето выгодно при n ≥ 10⁵–10⁶; для нескольких больших чисел — trial division.

Пример

Найдите все простые числа на отрезке [110; 130] и выведите их с порядковыми номерами.

from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False
    return True

k = 0
for n in range(110, 131):
    if is_prime(n):
        k += 1
        print(k, n)

Ответ1 113; 2 127.

По решениям № 706, 891, 896, 2590, 6149.

огромное N, ровно k делителей

Формулы τ(N) и σ(N): когда делители не перечислить

Когда использовать: N большое или известно разложение, а нужны количество или сумма делителей; либо нужно найти число с заданным числом делителей.

Разложите N на простые множители.
Для количества делителей перемножьте (ai + 1).
Для суммы делителей используйте сумму геометрической прогрессии по каждому p.
Для поиска числа с заданным τ переберите разбиения τ на множители (ai + 1).
Сопоставьте большие показатели меньшим простым числам и проверьте ограничение.

τ(360) = 24, σ(360) = 1170; сумма без 1 и N равна 809.
117 = 9 · 13 — один из вариантов: показатели 8 и 12 дают p⁸q¹².
1000 = 5 · 5 · 5 · 2 · 2 · 2; минимальное число 2⁴ · 3⁴ · 5⁴ · 7 · 11 · 13 = 810 810 000.
39 = 3 · 13: подходят p³⁸ и p²q¹².
Для полного квадрата все показатели чётны, поэтому τ нечётно.
Сумма без 1 и N: σ(N) - 1 - N.

Пример

Найдите количество и сумму всех натуральных делителей числа 360 по разложению.

from math import isqrt

def factor(n):
    f = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

def tau(n):
    r = 1
    for e in factor(n).values():
        r *= e + 1
    return r

def sigma(n):
    r = 1
    for p, e in factor(n).items():
        r *= (p ** (e + 1) - 1) // (p - 1)
    return r

print(tau(360), sigma(360))

Ответ24 1170.

По решениям № 2593, 5226, 5773, 5967, 7013.

пятый по величине, наибольший делитель

Парные делители: k-й, минимум и максимум

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

Наименьший нетривиальный делитель ищите с 2 вверх до первого найденного.
Наибольший собственный делитель составного N равен N // d_min.
k-й по величине нетривиальный делитель равен N // (k-й по возрастанию нетривиальный).
Для суммы пары добавляйте d + N // d; корень добавляйте один раз.
Делители около корня ищите от isqrt(N) вниз и вверх.

Для простого N нетривиальных делителей нет.
Пятый по величине нетривиальный делитель 1000: пятый маленький — 10, ответ 1000 // 10 = 100.
d_min — это наименьший простой делитель, поэтому max_proper = N // d_min.
Для N = p² есть только один нетривиальный делитель p.
Если нужны только первые k маленьких делителей, полный список можно не сортировать.

Пример

Найдите пятый по величине делитель числа 1000, не считая 1 и самого числа.

from math import isqrt

def divisors(n):
    ds = {1, n}
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            ds |= {d, n // d}
    return sorted(ds)

d = divisors(1000)[1:-1]   # без 1 и самого числа
print(d[-5])

Ответ100.

По решениям № 2869, 3024, 3025, 2479, 4276.

больше X, меньше X, первые пять

Поток чисел: первые и последние N

Когда использовать: В условии нет верхней границы или нужно найти первые (наибольшие) N чисел, удовлетворяющих условию.

Определите направление и старт: для «больше X» — X + 1, для «меньше X» — X - 1.
Идите циклом while, пока не набрано N найденных чисел.
Проверяйте дешёвые условия раньше полного перебора делителей.
Сразу после N-го найденного числа выходите из цикла.
Если ответ должен быть по возрастанию, соберите результаты и отсортируйте.

range(a, b + 1) — когда верхняя граница известна; while — когда её нет.
«Больше» и «меньше» строгие; «не превышает» включает границу.
При движении вниз удобно собирать ответ и затем перевернуть его.
Для «первых 7 чисел меньше 500 000» начинайте с 499 999 и уменьшайте x.
Не задавайте гигантский range: используйте while с выходом по счётчику.
Проверяйте, что найденных чисел действительно N, а не меньше из-за границы.

Пример

Найдите 5 наименьших чисел, больших 500 000, у которых есть делитель, оканчивающийся на 8, не равный 8 и самому числу. Для каждого выведите минимальный такой делитель.

from math import isqrt

def divisors(n):
    ds = {1, n}
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            ds |= {d, n // d}
    return sorted(ds)

found = 0
x = 500001
while found < 5:
    ds = [d for d in divisors(x) if d % 10 == 8 and d not in (8, x)]
    if ds:
        print(x, min(ds))
        found += 1
    x += 1

Ответ500002 178; 500004 18; 500016 48; 500018 58; 500020 4348.

По решениям № 1867, 2361, 2589, 2943, 3184.

делитель оканчивается на…, кратен…, даёт остаток

Особые делители: окончание, кратность, остаток

Когда использовать: Условие накладывается не на все делители, а на их десятичную запись, кратность или остаток от деления.

Найдите все делители числа или пары делителей.
Отфильтруйте их по последней цифре, диапазону или кратности.
Исключите 1 и N, если это требуется в условии.
Посчитайте количество, сумму, минимум или максимум по отфильтрованным.
Если подходящих нет, используйте 0, когда это предусмотрено условием.

Последняя цифра делителя: d % 10 == 7; последние две: d % 100.
«Делитель кратен 3» — d % 3 == 0; сам N тоже может попасть под фильтр.
«Ровно три делителя, оканчивающихся на 7» — len(filtered) == 3.
«Максимальный делитель, кратный трём» — max(filtered).
«Сумма делителей даёт остаток r» — sum(filtered) % m == r.
При переборе до √N оба делителя пары нужно проверять отдельно.

Пример

Найдите первые пять чисел, больших 550 000, у которых ровно три делителя оканчиваются на 7 и не равны самому числу. Для каждого выведите максимальный такой делитель.

from math import isqrt

def divisors(n):
    ds = {1, n}
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            ds |= {d, n // d}
    return sorted(ds)

found = 0
x = 550001
while found < 5:
    ds = [d for d in divisors(x) if d % 10 == 7 and d != x]
    if len(ds) == 3:
        print(x, max(ds))
        found += 1
    x += 1

Ответ550014 275007; 550017 1567; 550032 34377; 550035 110007; 550037 9017.

По решениям № 2361, 2589, 3197, 1867.

маска + делится на m

Маски и делимость: перебор кратных

Когда использовать: В условии есть маска и делимость на m, а предел достаточно велик, чтобы перебирать только кратные, а не все числа.

Перебирайте x = m, 2m, 3m, … до предела, а не каждое число подряд.
Проверяйте fnmatchcase(str(x), mask).
Добавьте остальные условия: цифры, делители, палиндром.
Печатайте x и x // m, если просят частное.
Если делитель мал, а предел огромен, переходите к генерации по маске.

range(m, limit + 1, m) включает предел, если он кратен m.
fnmatchcase учитывает регистр; для цифр это не важно, но функция надёжнее для точного сравнения.
«*» соответствует и пустой строке, «?» — ровно одному символу.
Маска без «*» автоматически задаёт точную длину числа.
Квадратные скобки в fnmatch — специальные; в экзаменационных масках их нет.
Для m = 17 и предела 10⁹ перебор кратных всё ещё велик: используйте метод 08.

Пример

Найдите все числа, не превышающие 10¹⁰, которые соответствуют маске 1?2139*4 и делятся на 2023. Выведите число и частное.

from fnmatch import fnmatchcase

for x in range(2023, 10**10 + 1, 2023):
    if fnmatchcase(str(x), '1?2139*4'):
        print(x, x // 2023)

Ответ162139404 80148; 1321399324 653188; 1421396214 702618; 1521393104 752048.

По решениям № 4711, 6637, 7251, 7255.

предел 10¹⁰+, мало «?», квадраты

Генерация по маске и обратный перебор

Когда использовать: Предел огромен, но маска оставляет мало свободы; или число связано с квадратом, кубом или другим малым параметром.

Посчитайте число «?»; если их немного, переберите цифры через product.
Подставьте цифры в шаблон и проверьте делимость.
Если есть «*», разбейте маску на фиксированные блоки и переберите длины пропусков.
Для условия «квадрат соответствует маске» перебирайте корень, а не само число.
Проверьте границу, отсутствие ведущего нуля и отсортируйте ответ.

Маска 1?34567?9 содержит два «?»: это 100 кандидатов вместо 59 миллионов кратных 17.
Для масок с «*» генерируйте только допустимые длины и фиксированные блоки.
Для «квадратов до 10¹⁰» перебирайте n до 10⁵ и проверяйте n².
Для «чисел с ровно k делителями» генерируйте p^a · q^b по разбиению k.
fnmatchcase на готовой строке — удобная финальная проверка.
Следите, чтобы первая цифра числа не была нулём.

Пример

Найдите все числа, не превышающие 10⁹, соответствующие маске 1?34567?9 и делящиеся на 17.

from itertools import product

for a, b in product('0123456789', repeat=2):
    x = int(f'1{a}34567{b}9')
    if x % 17 == 0:
        print(x, x // 17)

Ответ113456759 6673927; 133456749 7850397; 153456739 9026867; 173456729 10203337; 193456719 11379807.

По решениям № 3064, 3253, 4449, 5224, 6497.

маска + ровно k делителей, цифры + делители

Комбинированные условия: сначала строение числа

Когда использовать: Маска и свойство делителей даны одновременно, а прямой перебор невозможен. Строение числа резко сокращает число кандидатов.

Определите точное число делителей или другой признак.
Выпишите возможные разложения: например, τ = 9 даёт p⁸ или p²q².
Сгенерируйте все числа такого строения до предела.
Отфильтруйте их по маске, делимости и цифровым условиям.
Для каждого результата вычислите требуемый делитель или частное.

τ = 9: p⁸ или p²q²; при пределе 10⁹ кандидатов немного.
τ = 4: p³ или p · q; τ = 6: p⁵ или p² · q.
τ = 39: p³⁸ или p² · q¹²; τ = 117: p¹¹⁶ или p⁸ · q¹² и другие разбиения.
Простые числа до √(limit) удобно получить решетом один раз.
Наибольший собственный делитель = N // минимальный простой делитель.
Не забывайте про случаи с одной простой степенью: p⁸, p³⁸.

Пример

Найдите все числа до 10⁹, соответствующие маске 15*3*09 и имеющие ровно 9 делителей. Для каждого выведите наибольший делитель, не равный самому числу.

from fnmatch import fnmatchcase
from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False
    return True

limit = 10**9
ans = []

for p in range(2, 14):              # p^8
    if is_prime(p):
        n = p ** 8
        if n <= limit and fnmatchcase(str(n), '15*3*09'):
            ans.append((n, p))

for p in range(2, isqrt(limit) + 1):  # p^2 * q^2
    if not is_prime(p):
        continue
    for q in range(p + 1, isqrt(limit // (p * p)) + 1):
        if is_prime(q):
            n = (p * q) ** 2
            if n <= limit and fnmatchcase(str(n), '15*3*09'):
                ans.append((n, p))

for n, p in sorted(ans):
    print(n, n // p)

Ответ15233409 5077803; 153834409 1947271; 158835609 52945203.

По решениям № 5225, 5985, 6210, 7013, 7044.

Шпаргалка: формулировка → метод

В условии	Что делать
«ровно k различных делителей»	перебор до √N; при большом k — формула τ и строение числа
«не считая 1 и самого числа»	нетривиальные делители; количество = τ − 2
«ровно три нетривиальных делителя»	N = p⁴, а не p²
«нечётное количество делителей»	N — полный квадрат
«нечётное количество чётных делителей»	N = 2t²
«ровно три чётных делителя»	N = 8 или N = 2p² (если N считается); иначе 16, 4p, 2p³ или 2pq
«сумма и произведение делителей нечётны»	N — нечётный квадрат
«пятый по величине делитель»	пятый наименьший d, ответ N // d
«наибольший/наименьший делитель»	пара d и N/d; max = N // min
«сумма делителей кратна m»	σ без 1 и N, затем остаток
«делитель оканчивается на d»	фильтр d % 10 == digit
«маска ? и *»	fnmatchcase + перебор кратных
«предел 10¹⁰ и больше»	генерировать по маске или строению числа
«первые 5 чисел больше X»	while с ранним выходом
«квадраты/кубы соответствуют маске»	перебирать корень, а не число
«ровно 9/25/39/117 делителей»	разложение показателей: 9=3·3, 25=5·5, 39=3·13, 117=9·13
«число вида 2^m · 3^n»	двойной цикл по m и n
«ответ — частное»	не забыть x // d

Видеоразборы по теме

Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.

По базе Kompege: 1 075 задач по заданию 25, 124 решения (119 программных и 5 текстовых) и 241 видеоразбор (144 YouTube, 63 VK, 34 Rutube). Около 490 задач сформулированы про делители, 462 — про маски, 102 совмещают оба условия. Для методов отобраны решения задач № 22, 67, 106, 892, 893, 1206, 1762, 1867, 2361, 2593, 2869, 3024, 3064, 4711, 5225, 5985 и 6276; примеры переработаны в учебные.

Разборы из видео

Задачи, которые разбирают в курсе

Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.

№ 2570

разбор из видео · 2026

Числа с ровно 6 делителями

Найдите числа на отрезке [135743; 135789], имеющие ровно 6 различных делителей. Для каждого выведите два наибольших делителя в порядке возрастания.

def div(x):
    d = set()
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            d.add(i)
            d.add(x // i)
    return sorted(d)

for x in range(135743, 135790):
    d = div(x)
    if len(d) == 6:
        print(d[-2], d[-1])

Ответ45249 135747; 67874 135748; 67882 135764; 27155 135775

Смотреть с 15:30

Полный архив

Все фрагменты видеоразборов

По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.

Показать все фрагменты (43)

2026 · 00:00 Приветствие

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 00:00

2026 · 01:55 Как искать делители числа 2570

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 01:55

2026 · 15:30 Числа с 6 делителями 2570

d = set()
for i in range(1,int(x**0.5)+1):
return sorted(d)
for x in range(135743,135790):
if len(d)==6:

Смотреть с 15:30

2026 · 20:05 Числа с 3 нечётными делителями 2573

ищет среди целых чисел, принадлежащих числовому различных НЕЧЁТНЫХ делителя. В ответе для кажлого найденного числа запишите два его наибольших нечётных делителя в порядке убывания.

def div(x):
d = set()
for i in range(1,int(x**0.5)+1):
if x%1==0
return sorted(d)
for x in range(190061, 190073):
d = [i for i in div(x) if i%2!=0]
if len(d)==4:

Смотреть с 20:05

2026 · 24:40 Сумма сумма макс и мин делителя 7502

максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение М считается равным нулю. Например, для числа 20 имеем М Напишите программу, которая перебирает целые числа, меньшие 300 000, в порядке убывания и ищет среди них такие, для которых значение М оканчивается на 2. В ответе запишите в первом "столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце — соответствующие им значения М.

def div(x):
d = set()
for i in range(2, int(x**0.5)+1):
if x%:
return sorted(d)
for x in range(799_000, 800_000):
if len(d)>0:
M = max(d)+min(d)
if M%10==2:
print(x,M)

Смотреть с 24:40

2026 · 34:55 Делители, оканчивающиеся на 7 и не равные 7 8076

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

def div(x):
d = set()
for i in range(2, int(x**0.5)+1):
if x%i==0:
return sorted(d)
if len(d)>0:

Смотреть с 34:55

2026 · 40:10 Сумма делителей числа 4115

for i in range(2, int(x**0.5)+1):
for x in range(150_001,151_000):

Смотреть с 40:10

2026 · 43:25 Среднее арифметическое делителей числа

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 43:25

2026 · 47:00 Работа с простыми числами 2837

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

Смотреть с 47:00

2026 · 1:06:35 Числа с 6 простыми делителями I способ 2837

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

while x%i==0:
x = xX//i
return sorted(set(d))
d = fact(x)
if Len(d)>=6:
print(x, fnax(d))

Смотреть с 1:06:35

2026 · 1:12:10 Числа с 6 простыми делителями II способ 4116

Обозначим через $ сумму простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение $ равным нулю. Hamme программу, которая перебирает целые числа, большие 250000 в порядке возрастания и ищет среди них такие, для которых значение $ не равно нулю и кратно 17. Программа должна найти первые 5 таких чисел. в отдельной строке сначала выводится само число, затем значение $. Строки выводятся в порядке возрастания найденных чисел.

Смотреть с 1:12:10

2026 · 1:16:15 Cумма простых делителей I способ

return sorted(set(d))
s = sum(d)

Смотреть с 1:16:15

2026 · 1:20:35 Cумма простых делителей II способ

return sorted(set(d))
def div(x):
d = set()
for i in range(2,int(xa+0, 5)+1):
if x%:
return sorted(d)

Смотреть с 1:20:35

2026 · 1:23:45 Сумма макс и мин простых делителей I способ

минимального числа срели простых делителей пелого числа №. не считая самого числа. Если таких делителей у числа нет, To считаем значение МСК) равным нулю. Найдите первые 6 чисел, больших 23 600 000, для которых значение M(N) при делении на 213 даёт в остатке 171. В ответе запишите найденные числа в порядке возрастания, справа от кажлого запишите соответствующее значение МОХ.

d= [1]
while 1=2
while x¥i==0:
if 1 =x//1
for x in gl return d
M = max(d)+min(d)
if M%213==171:

Смотреть с 1:23:45

2026 · 1:28:35 Сумма макс и мин простых делителей II способ 2328

делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение М считается равным нулю. Напишите программу, которая перебирает целые числа, большие 5 400 000, в порядке возрастания и ищет среди них такие, для которых М больше 60 000 и является палиндромом, т.е. одинаково читается слева направо и "справа налево. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце - соответствующие им значения М. Количество строк в таблице для ответа избыточно.

Смотреть с 1:28:35

2026 · 1:32:10 Сумма макс и мин простых делителей ПАЛИНДРОМ I способ

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

while ixs2<:
while x¥i==0:
if x>1:
return d
if len(d)>0:
M = max(d)+min(d)

Смотреть с 1:32:10

2026 · 1:36:55 Сумма макс и мин простых делителей ПАЛИНДРОМ II способ

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:36:55

2026 · 1:38:40 Макс нетривиальный делитель НЕ простое число

def div(x):
d = set()
for i in range(2,int(xex0.5)+1):
if x%i
dl={i,x//i}
return sorted(d)
for x in range(450_001,451_000):
if Len(d)>0:
M = max(d)
if Len(div(m))>0:
print(x,M)

Смотреть с 1:38:40

2026 · 1:44:35 Числа произведения ровно 2 простых множителей 24331

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

Смотреть с 1:44:35

2026 · 1:50:30 Числа произведения ровно 5 простых множителей 24331

while ixi<=:
while x%1==0:
return d
for x in range(13_475_125,13_500_000):
d = fact(x)
if len(d)

Смотреть с 1:50:30

2026 · 1:54:00 Числа произведения ровно 12 простых множителей 8393

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

while x%1 :
x=x//1
return d
d = fact(x)
if len(d)==12:

Смотреть с 1:54:00

2026 · 1:56:40 РОЗЫГРЫШ 8393

while 1*1<=
while x%; :
x=x//1
return d
for x in range(24_517_513, 24_600_000):

Смотреть с 1:56:40

2026 · 2:16:15 Числа с 3 нетривиальными делителями 2839

Найдите все натуральные числа, принадлежащие Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

for i in range(2, int(x**0.5)+1):
if x®i
return sorted(d)
for i in range(18938,23145):
xX = ine?
d = div(x)
if len(d)==3:
print(x,max(d))

Смотреть с 2:16:15

2026 · 2:23:45 Числа с 3 чётными делителями

В ответе перечислите найденные числа, справа от каждого числа запишите его наибольший нечётный делитель.

Смотреть с 2:23:45

2026 · 2:36:50 Числа с 5 нечётными делителями 3779

В ответе перечислите найденные числа, справа от каждого числа запишите его наибольший нечётный делитель.

def div(x):
d = set()
if x®i==0:
dl={i,x//i}
return sorted(d)
for x in range(78_000_000,85_000_001):

Смотреть с 2:36:50

2026 · 2:44:30 Минимальное число с 512 делителями 3927

Богданов) Найдите наименьшее натуральное число, которое é имеет ровно 512 делителей. В ответе запишите сначала само число и затем его наибольший простой делитель.

Смотреть с 2:44:30

2026 · 2:59:25 Окончание и напутствие 3927

Богданов) Найдите наименьшее натуральное число, которое & имеет ровно 512 делителей. В ответе запишите сначала само число и затем его наибольший простой делитель.

Смотреть с 2:59:25

2026 · 00:00 Приветствие

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 00:00

2026 · 02:10 Что такое маска

- символ * означает любую последовательность цифр произвольной длины; в том числе * может задавать и пустую последовательность. Например, маске 1234475 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 1*237756, делящиеся на 171 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 171. Количество строк в таблице для ответа избыточно.

Смотреть с 02:10

2026 · 04:40 Решение через fnmatch I

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ ? означает ровно одну произвольную цифру; - символ * означает любую последовательность цифр произвольной длины; в том числе * может задавать и пустую последовательность. Например, маске 123*475 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 103, найдите все числа, соответствующие маске 1*237756, делящиеся на 171 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 171. Количество строк в таблице для ответа избыточно.

from fnmatch import *
for x in range(0,10*%8,171):

Смотреть с 04:40

2026 · 08:25 Решение через fnmatch II

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: 1) символ 2 означает ровно одну произвольную цифру; 2) символ * означает любую последовательность цифр произвольной длин задавать и пустую последовательность Например, маске 123*425 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 107°, найдите все числа, соответствующие маске 1*232272, делящиеся на 2024 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором том числе * может

Смотреть с 08:25

2026 · 09:50 Решение через fnmatch III 15340

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: 1) символ ? означает ровно одну произвольную цифру; 2) символ * означает любую последовательность цифр произвольной длины; в том числе * может "задавать и пустую последовательность. Например, маске 123*425 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 1070, найдите все числа, соответствующие маске 1*232272, делящиеся на 2024 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце - соответствующие им результаты деления этих чисел на 2024. Количество строк в таблице для ответа избыточно.

from fnmatch import *
for x in range(0,10**10,2024):
if fnmatch(str(x),'1*2322?2'):
print(x,x//2024)

Смотреть с 09:50

2026 · 11:50 Подстановка в маску I 6655

Джобс) Назовём маской числа последовательность пифр, в которой также могут встречаться следующие символы: — символ ? означает ровно одну произвольную цифру: числе * может задавать и пустую последовательность. Например, маске 123*425 соответствуют числа 123405 и 12300425. Найдите все числа, меньшие 1012, соответствующие маске 12324*5679 и деляшиеся без остатка на 4013. В качестве ответа приведите все найденные числа в порядке возрастания, справа от каждого числа выведите результат его деления на 4013.

Смотреть с 11:50

2026 · 19:20 Подстановка в маску II

Например, маске 123*425 соответствуют числа 123405 и 12300425. Найдите все числа, меньшие 1012, соответствующие маске 12324*5679 и деляшнеся без остатка на 4013. В качестве ответа приведите все найденные числа в порядке возрастания, справа от каждого числа выведите результат его деления на 4013.

from itertools import *
comb = []
if x%4013
print(x,x//4013)

Смотреть с 19:20

2026 · 27:05 Решение через fnmatch IV 6655

Джобс) Назовём маской числа последовательность пифр, в которой также могут встречаться следующие символы: — символ 2 означает ровно одну произвольную пифру; числе * может задавать и пустую последовательность. Например, маске 123*425 соответствуют числа 123405 и 1230042 Найдите все числа, меньшие 1012, соответствующие маске 12324*5679 и деляшиеся без остатка на 4013. В качестве ответа приведите все найденные числа в порядке

from itertools import *
comb = []
for x in product( '0123456789' ,repeat=1):
for al in '0123456789':
for a2 in comb:
x = int(f'123{a1}4{a2}5679')
if x%4013==0:
print(x,x//4013)

Смотреть с 27:05

2026 · 30:00 Подстановка в маску III 6190

Сорокин) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ @ означает любую последовательность может задавать и пустую последовательность. означает одну любую цифру. соответствуют числа 190, 13591, Найдите все натуральные числа, которые не превышают 101, соответствуют маске 78256@321 и делятся на 279. В ответе запишите все найденные числа в порядке "возрастания, а справа от каждого число — частное от — деления этого числа на 279.

Смотреть с 30:00

2026 · 40:25 Подстановка в маску IV 5618

Багдасарян) Назовём маской числа последовательность пифр, в которой также могут встречаться следующие символы: - символ Ч означает ровно одну произвольную четную пифру: - символ Н означает ровно одну произвольную нечетную цифру: чисел, не превышающих 108, найдите все числа, соответствующие маске 123*НЧ56, "результаты деления этих чисел на 206.

Смотреть с 40:25

2026 · 49:20 Подстановка в маску V

from itertools import *
comb = []
for 1 in 0,1:
for x in product('0123456789',repeat=1):

Смотреть с 49:20

2026 · 52:30 Решение через fnmatch V

Багдасарян) Назовём маской числа последовательность пифр, в которой также могут встречаться следующие символы: - символ Ч означает ровно одну произвольную четную пифру; = символ Н означает ровно одну произвольную нечетную пифру; * может задавать и пустую последовательность. Например, маске *ЧН2 соответствуют числа 7232, 612, 444692 и тд. чисел, не превышаюших 108, найдите все числа, соответствующие маске 133*НЯ56, делящиеся на 206 без остатка. В ответе запишите в первом столбие таблицы все "найденные числа в порядке возрастания, а во втором столбие — соответствующие им о mien 5 —- — результаты деления этих чисел на 206.

from itertools import *
comb = []
for 1 in 0,1:
for x in product('0123456789' ,repeat=U):
for a1 in comb:
from fnmatch import *
for x in range(0,10**8,206):
if fnmatch(str(x), '123*[13579][02468]56'):

Смотреть с 52:30

2026 · 55:10 Подстановка в маску VI

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 55:10

2026 · 1:01:00 Решение через fnmatch VI 5857

Петров) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ 2 означает ровно одну произвольную — символ * означает любую последовательность задавать и пустую последовательность. Например, маске 123*425 соответствуют числа 123405 1 Среди натуральных чисел, не превышающих. 109, найдите все числа, семеричная запись которых. соответствует маске 2213*5664, делящиеся на 33310 без остатка. В ответе запишите все найденные числа в соответствующие им частные OT деления на 33310. числа в ответе запишите в десятичной системе

Смотреть с 1:01:00

2026 · 1:04:25 Подстановка в маску VII 5857

if x%333:
for x in sorted(ans):
print(x,x//333)

Смотреть с 1:04:25

2026 · 1:08:50 Окончание и напутствие 6655

Джобс) Назовём маской числа последовательность пифр, в которой также могут встречаться следующие символы: — символ ? означает ровно одну произвольную пифру; числе * может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все числа, меньшие 1012, соответствующие маске 15374*5679 и деляшиеся без остатка на 4013. В качестве ответа приведите все найденные числа в порядке возрастания, справа от каждого числа выведите результат его деления на 4013.

for a1 in '0123456789':
for a2 in comb:
if x%4013
print(x,x//4013)

Смотреть с 1:08:50

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

единица считается простой
путают «ровно k делителей» и «ровно k нетривиальных делителей»
забывают пару d и N/d или добавляют корень дважды
не исключают 1 и само число, когда это требуется
перебирают весь диапазон там, где достаточно кратных или кандидатов по маске
путают делитель и частное от деления
нарушают порядок вывода: по возрастанию, по убыванию, сначала N или сначала делитель
слишком медленный алгоритм

Практика

ФИПИОткрытый банк заданий Навигатор · 2026Алгоритмы ДемоверсияКИМ 2027 МетодикаРазбор ошибок 2026

Навигатор и методические рекомендации опубликованы в 2026 году: номера заданий в них могут отличаться от нумерации 2027 года. Ориентируйтесь на тему.