Статья Автор: Деникина Н.В., Деникин А.В.

Вопрос 25. Паттерны

ЕГЭ по информатике · паттерны

Задание 25

Один универсальный каркас и небольшая библиотека функций — делители, факторизация, простые числа, маски, — которые закрывают практически любую формулировку задания за 2021–2026 годы. Сначала каркас, затем восемь типов как его настройки.

1 первичный баллрешения на Pythonуниверсальный каркас9 разделовпроверенные ответы
00

Универсальный каркас

«Два скелета и одна библиотека — всё остальное это их настройка»

Любое задание 25 распадается на две схемы. Если в условии есть маска (символы ? и *) — работает каркас Б (перебор по кратным). Во всех остальных случаях — каркас А (перебор отрезка + характеристика числа + фильтр). Дальше меняются только функция-характеристика, условие и то, что выводим.

for i in range(A, B + 1):       # 1. перебор отрезка [A; B]
    x = характеристика(i)       # 2. divisors / factorize / prime_set
    g = фильтр(x)               # 3. отбор по свойству из условия
    if условие(g):              # 4. порог: ==K / >=K / sum>L ...
        print(нужные_поля)      # 5. вывод РОВНО того, что просят
for x in range(m, 10**10 + 1, m):   # перебор ТОЛЬКО кратных m
    if по_маске(str(x)) and доп(x): # fnmatch или re.fullmatch
        print(x, x // m)            # обычно во 2-м столбце частное

Библиотека (вставляй нужные функции в начало)

import math
def divisors(n):                # ВСЕ натуральные делители за √N
    divs = set();
    for d in range(1, math.isqrt(n)+1):   # isqrt - возвращает целую часть кв. корня n   
        if n % d == 0:
            divs.add(d) 
            divs.add(n // d)   # парный делитель; set убирает дубль квадрата
    return divs  # возвращаем множество делитлей (в произвольном порядке!)

Все натуральные делители за √N. 

def factorize(n):               # разложение СО СТЕПЕНЯМИ: {p: a, q: b, ...}
    f = {}; d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1; n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1   # оставшийся крупный простой множитель
    return f

Разложение со степенями. Отсюда сразу: простые делители set(f), сумма показателей sum(f.values()), число разных простых len(f). Нужна в разделах 03, 06.

def num_div(n):                 # число делителей = произведение (a+1) — БЕЗ перебора
    r = 1
    for a in factorize(n).values():
        r *= a + 1
    return r

Число делителей формулой ∏(a + 1) — без построения множества делителей. Незаменима на больших числах (раздел 06) и для «ровно K делителей» (раздел 03).

def is_prime(n):                # проверка простоты за √N
    if n < 2: return False
    d = 2
    while d * d <= n:
        if n % d == 0: return False
        d += 1
    return True

Проверка простоты за √N. Нужна в разделе 04 (поиск простых) и как доп. условие в разделе 09. Для больших отрезков — решето из раздела 04.

Как читать условие — выбор каркаса и функции

  1. В условии есть маска (?, *) и делимость на m? → каркас Б (разделы 08–09).
  2. Нужны все делители (количество, сумма, наибольший, делитель со свойством)? → divisors() (разделы 01, 02, 05, 07).
  3. Речь о простых множителях, их количестве, степенях, или о числе делителей формулой? → factorize() / num_div() (разделы 03, 06).
  4. Надо проверить простоту или найти простые на отрезке / с номером? → is_prime() или решето (раздел 04).
  5. Последний шаг всегда один: вывести ровно те поля и в том порядке, что просит условие.

Три ошибки, общие для всех типов

  • Что исключать. «Не считая 1 и самого числа» / «не считая самого числа» / «все натуральные делители» — три разных множества.
    divisors(i) - {1, i} - не считая 1 и самого числа
    divisors(i)- {i} - не считая самого числа.
    Самая частая потеря балла.
  • Границы отрезка включительно: [A; B] → range(A, B + 1).
  • Float-корень. int(n ** 0.5) может вызвать переполнение на достаточно больших n; math.isqrt(n) - надёжнее.
01

Подсчёт делителей за √N

«Фундамент всего семейства делителей»

Признаки в условии

  • «ровно / не менее / не более K делителей»
  • оговорка «не считая единицы и самого числа» (или другая)
  • вывести количество делителей и наибольший из них

Идея

Делители идут парами: если d делит n, то и n // d тоже — хватает перебора до √N. Функция divisors() — из каркаса.

Настройка каркаса А

for i in range(A, B + 1):
    d = divisors(i) - {1, i}    # читай условие: что исключать!
    if len(d) >= K:
        print(len(d), max(d))

Ловушки

  • Что исключать. Перечитай дословно: «не считая 1 и самого» vs «все натуральные» — получим разное K - количество делителей числа.
  • max(d) на пустом множестве упадёт — для простых i множество d пустое.

Тренировка

Задача 1 — не менее K делителей

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

Показать ответСкрыть ответ
d = divisors(i) - {1, i},
 условие len(d) >= 8, вывод len(d), max(d): 108 10 54
112 8 56
120 14 60
02

Сумма и чётность делителей

«Фильтруем делители по свойству при переборе»

Признаки в условии

  • «сумма делителей больше L»
  • «только чётные (или нечётные) делители» — их количество, максимум или сумма

Идея

Свойство проверяем и у делителя d, и у парного e = i // d — за один шаг обрабатываем двух кандидатов. Копим в set, чтобы не было дублей.

Настройка — только чётные делители (тип демоверсии)

import math

def divisors_evens(n):               
    divs = set(); 
    for in range(2, math.isqrt(n)+1):
        if i % d == 0:
            if d % 2 == 0: divs.add(d)
            e = i // d
            if e % 2 == 0: divs.add(e)   # чётность e проверяем ОТДЕЛЬНО
     return divs

суммасумма делителей > L

for i in range(A, B + 1):
    d = divisors(i) - {1, i}   
    if sum(d) > L:
        print(i, sum(d))

нечётколичество чётных не более K

for i in range(A, B + 1):
    s = divisors_evens(i) - {1, i} 
    if len(s) >= K:
        print(len(s), max(s))

Ловушки

  • Само число и единицу включай в сумму строго по условию — формулировки разные.
  • Чётность d ничего не говорит о чётности e. Чётность парного e = i // d проверяй отдельно от d:

Тренировка

Задача 2 — чётные делители

Среди чисел отрезка [200; 260] найдите те, у которых не менее 10 чётных делителей. Для каждого выведите количество чётных делителей и наибольший из них.

Показать ответСкрыть ответ
Копим чётные d и e в set, условие len(s) >= 10: 216 11 108
240 15 120
252 11 126
похожая с ЕГЭ →
Задача 3 — сумма собственных делителей

Среди чисел отрезка [90; 100] найдите те, у которых сумма делителей (не считая 1 и самого числа) больше 100. Выведите число и эту сумму.

Показать ответСкрыть ответ
d = divisors(i) - {1, i}, условие sum(d) > 100: 90 143
96 155
100 116
похожая с ЕГЭ →
03

Факторизация и степени

«Разложение на множители со степенями — и число делителей без перебора»

Признаки в условии

  • «простые делители»: минимальный, максимальный, их количество, сумма или разность
  • число большое, а спрашивают количество делителей — перебор делителей долог, нужна формула

Идея

factorize() хранит степени:{p: a, q: b, ...}. Отсюда сразу: число делителей =(a + 1)*(b+1)*..., количество разных простых = len(f).
Множество set(f) заменяет старый prime_factors.

Что достаём из одного разложения

f = factorize(i)            # {p: a, q: b, ...}
primes   = set(f)           # различные простые делители
omega    = len(f)           # сколько РАЗНЫХ простых
big_omega = sum(f.values()) # сумма показателей (с кратностью)
ndiv     = num_div(i)       # число делителей = произведение (a+1)
# пример: 720 = 2^4 · 3^2 · 5^1 → primes={2,3,5}, omega=3,
#         big_omega=7, ndiv=(4+1)(2+1)(1+1)=30

разностьmax − min простого делителя

for i in range(A, B + 1):
    p = set(factorize(i))
    # хотя бы два разных простых
    if len(p) >= 2:         
        print(i, max(p) - min(p))

формуларовно K делителей у больших чисел

for i in range(A, B + 1):
    # без построения множества 
    # делителей
    if num_div(i) == K:     
        print(i)            
# быстро даже при больших i

Ловушки

  • Простые делители ≠ натуральные делители: не путай с разделом 01.
  • У простого i разложение это {i: 1}: один простой делитель, разность = 0. Если условие требует «не считая самого числа» — убери его и задай спец-значение.
  • Не теряй степени: для «суммы показателей» нужен именно factorize, а не set простых.

Тренировка

Задача 4 — разность простых делителей

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

Показать ответСкрыть ответ
p = set(factorize(i)); 90=2·3·5, 91=7·13, 92=2²·23, 93=3·31: 90 3
91 6
92 21
93 28
похожая с ЕГЭ →
Задача 5 — число делителей по формуле

Сколько делителей у чисел 2025, 720 и 1 000 000? Найдите через разложение, не перебирая делители.

Показать ответСкрыть ответ
num_div(n) = произведение (a+1): 2025 = 3⁴·5² → (4+1)(2+1) = 15
720 = 2⁴·3²·5 → 5·3·2 = 30
1000000 = 2⁶·5⁶ → 7·7 = 49
04

Поиск простых чисел

«Проверка простоты, решето и простое с номером»

Признаки в условии

  • «найдите все простые числа на отрезке», часто с порядковым номером
  • «найдите K-е простое, большее N» / «первые K простых»
  • отрезок очень большой (миллионы) — нужен решето вместо проверки каждого

Идея

На обычном отрезке хватает is_prime() из каркаса (проверка за √N).

Если перебираем миллионы или считаем простые в большом диапазоне используем решето Эратосфена: один проход вычёркивает все составные.

Простые на отрезке с порядковым номером

num = 0
for i in range(A, B + 1):
    if is_prime(i):
        num += 1
        print(num, i)          # слева номер, справа само простое

решетобыстро на большом N

def sieve(N):
  p = [True] * (N + 1)
  p[0] = p[1] = False
  i = 2
  while i * i <= N:
    if p[i]:
      for j in range(i * i, N + 1, i):
        p[j] = False
    i += 1
    return p                    
# p[k] == True ⇔ k простое

с номеромK-е простое после N

cnt = 0; n = N
while cnt < K:
    n += 1
    if is_prime(n):
        cnt += 1
print(n)                        
# это и есть K-е простое > N

Ловушки

  • is_prime начинается с n < 2 → False: 0 и 1 не простые, иначе перебор их пропустит как «простые».
  • Решето требует памяти O(N): для N ~ 10⁷–10⁸ это нормально, для 10¹⁰ — нет (там обычно маски, раздел 08).
  • «K-е простое после N» — это бесконечный перебор до набора K штук, а не отрезок.

Тренировка

Задача 6 — простые с номером

Среди чисел отрезка [100; 114] найдите все простые. Выведите их по возрастанию, слева от каждого — порядковый номер в последовательности.

Показать ответСкрыть ответ
Счётчик num, печать num, i при is_prime(i): 1 101
2 103
3 107
4 109
5 113
05

Квадраты и «ровно N делителей»

«Особые структуры количества делителей»

Признаки в условии

  • «ровно два делителя, кроме 1 и самого числа»
  • «точный квадрат» или «число делителей нечётно»

Идея

Количество делителей числа n > 1 нечётно тогда и только тогда, когда n — точный квадрат (непарный делитель один — это √n). А «ровно два собственных делителя» означает 4 делителя всего: это p·q или p³.

Настройка — ровно два собственных делителя

for i in range(A, B + 1):
    d = divisors(i) - {1, i}
    if len(d) == 2:
        print(i, max(d))

квадратыперебор k²

k = 1
for i2 in range(isqrt(A), isqrt(B)+1:
    i = i2*i2
    d = divisors(i)
    ...

'''
если понимаем, 
что число может быть 
только точным квадратом, 
то перебираем квадраты
'''

через делителинечётное их число

for i in range(A, B + 1):
    if len(divisors(i)) % 2 == 1:
        print(i)               

# i — точный квадрат, 
# если количество делителей нечётно
'''
на больших диапазонах 
работает долго
'''

Ловушки

  • Двойной учёт √n у точного квадрата: set спасает, список — нет.
  • «Ровно два делителя» — уточни, считая 1 и само число или нет. Обычно «кроме 1 и самого» ⇒ всего делителей четыре.

Тренировка

Задача 7 — ровно два собственных делителя

Среди чисел отрезка [20; 30] найдите те, у которых ровно два делителя, не считая единицы и самого числа. Для каждого выведите само число и его наибольший делитель (кроме самого числа).

Показать ответСкрыть ответ
d = divisors(i) - {1, i}, условие len(d) == 2: 21 7
22 11
26 13
27 9
похожая с ЕГЭ →
Задача 8 — точные квадраты на отрезке

Выведите все точные квадраты на отрезке [100; 200] по возрастанию.

Показать ответСкрыть ответ
Перебор k*k от 1, пока k*k <= 200, печать при k*k >= 100: 100 121 144 169 196
06

Оптимизированный перебор

«Много делителей на большом диапазоне — идём по квадратам»

Признаки в условии

  • «найдите числа, имеющие ровно 117 (или иное нечётное) различных натуральных делителей»
  • отрезок большой (до 10⁸–10⁹) — наивный перебор не укладывается во время
  • дословно из ЕГЭ: «среди целых чисел, принадлежащих отрезку [A; B], найдите числа, имеющие ровно K делителей; выведите их в порядке возрастания»

Идея

Число делителей нечётно тогда и только тогда, когда n — точный квадрат: непарный делитель ровно один — это √n. Значит при нечётном требуемом K перебираем не все i, а только квадраты k², k от ⌈√A⌉ до ⌊√B⌋. Проверок становится √B − √A вместо B − A.

Каркас — поиск по квадрату (K нечётно)

from math import isqrt
# num_div() — из каркаса 00 (число делителей через ∏(a+1))
A, B, K = 900000, 2000000, 117      # 117 нечётно → только квадраты

k = isqrt(A)
if k * k < A:
    k += 1                          # стартуем с ⌈√A⌉
while k * k <= B:
    n = k * k
    if num_div(n) == K:
        print(n)
    k += 1

скорость10⁶ проверок → 10²

На [900000; 2000000] наивный перебор это 1 100 001 проверок (~20 с), по квадратам — всего 467 (~0,01 с). Ответ один и тот же.

почемуоба ответа — квадраты

921600 = 2¹²·3²·5² = 960², число делителей (12+1)(2+1)(2+1) = 117. И 1806336 = 1344². Нечётное K не оставляет другого варианта.

Ловушки

  • Трюк с квадратами годится только при нечётном K. Для чётного K число не обязано быть квадратом — перебирай обычным каркасом (диапазон тогда, как правило, умеренный).
  • Бери целочисленный корень isqrt, а не int(B**0.5): float на больших B теряет точность и пропускает граничный квадрат.
  • Считай делители формулой num_div, а не строй множество divisors() для каждого кандидата — на больших числах это снова медленно.
  • Стартовый k это ⌈√A⌉: пропустишь — либо потеряешь нижнюю границу, либо начнёшь ниже A.

Тренировка

Задача 9 — ровно 117 делителей на большом отрезке

Среди целых чисел, принадлежащих отрезку [900 000; 2 000 000], найдите все, имеющие ровно 117 различных натуральных делителей. Выведите их в порядке возрастания.

Показать ответСкрыть ответ
117 нечётно → перебираем только k² и проверяем num_div(k*k) == 117: 921600
1806336
921600 = 960², 1806336 = 1344² — оба точные квадраты.
похожая с ЕГЭ →
Задача 10 — разложение: наибольший простой делитель

Каждое число раскладывается на простые множители. Для каждого числа отрезка [180; 188] выведите само число и его наибольший простой делитель.

Показать ответСкрыть ответ
max(factorize(i)); например 184 = 2³·23 → 23, а 181 простое → делитель само число: 180 5
181 181
182 13
183 61
184 23
185 37
186 31
187 17
188 47
похожая с ЕГЭ →
07

Делитель со свойством

«Фильтр делителей по цифре и крайним значениям»

Признаки в условии

  • «делитель, оканчивающийся на 7» («семёрочный») и подобные свойства цифр
  • «разность наибольшего и наименьшего делителя»

Идея

Берём divisors() и фильтруем по нужному свойству. Аккуратно учитываем оговорённые исключения (например, «не равен самому числу и числу 7»).

Настройка — «семёрочные» делители

for i in range(A, B + 1):
    good = [x for x in divisors(i)
            if x % 10 == 7 and x != i and x != 7]
    if good:
        print(i, len(good), max(good))

разностьmax − min делителя

for i in range(A, B + 1):
  d = divisors(i) - {1, i}
  if if len(d) >= 1:
    M = max(d) - min(d)  
  else:
    M = 0      # нет делителей → 0
  print(i, M)       

старше Nпервые 5 подходящих

cnt = 0; n = 700000
while cnt < 5:
  n += 1
  if any(x % 10 == 7 and x!= n and x != 7
           for x in divisors(n)):
      print(n)
      cnt += 1

Ловушки

  • Исключения в условии (делитель != i, != 7) пропустишь — получишь лишние совпадения.
  • «Нет подходящих делителей» или min == max → результат 0 (обработай явно).
  • Формулировка «перебирает числа, большие N» означает бесконечный перебор до набора нужного количества — не отрезок.

Тренировка

Задача 11 — есть «семёрочный» делитель

Среди чисел отрезка [220; 235] найдите те, у которых есть делитель, оканчивающийся на цифру 7 (не считая делителей, равных самому числу и числу 7). Выведите такие числа по возрастанию.

Показать ответСкрыть ответ
Фильтр x % 10 == 7 and x != i and x != 7; например 221=13·17, 235=5·47: 221 222 228 231 234 235
08

Маска и делимость

«Перебор по кратным + fnmatch — формат демоверсии ФИПИ»

Признаки в условии

  • «назовём маской числа последовательность цифр…», символы ? и *
  • «найдите числа, соответствующие маске и делящиеся на m»; второй столбец — частное

Идея

Числа огромны (до 1010), всё подряд перебирать нельзя — это каркас Б. Спасает делимость: перебираем только кратные m и сверяем строку с маской через fnmatch.

Каркас Б — маска + делимость

from fnmatch import fnmatch

mask = '3?12?14*5'     # ? — одна цифра, * — любая последовательность
m = 1917
for x in range(m, 10**10 + 1, m):    # шаг m: только кратные m
    if fnmatch(str(x), mask):
        print(x, x // m)             # во втором столбце частное

Шпаргалка по маскам

?одна цифра

? — ровно один произвольный символ. В маске числа это ровно одна цифра 0–9.

*любая длина

* — любая последовательность, в том числе пустая. Маске 3?12?14*5 подходит и короткое 3121465.

шагкратные m

range(m, 10**10 + 1, m) — перебираем только числа, кратные m. Это и делает задачу решаемой.

strсравнение строк

fnmatch работает со строками — число превращаем в str(x). Сравнение учитывает ? и * ровно как в маске.

Ловушки

  • Перебор всех чисел до 1010 — зависание (TLE). Перебирай по кратным m.
  • У числа нет ведущих нулей, но * может быть пустым — учитывай это, прикидывая минимальную длину.
  • Забыть str(x): fnmatch ждёт строку, а не число.

Тренировка

Задача 12 — маска + делимость

Среди натуральных чисел, не превышающих 500, найдите все соответствующие маске *7 и делящиеся на 13 без остатка. Выведите числа по возрастанию и частное от деления каждого на 13.

Показать ответСкрыть ответ
for x in range(13, 501, 13), проверка fnmatch(str(x), '*7'), печать x, x // 13: 117 9
247 19
377 29
09

Маски с условиями

«Дополнительные ограничения и переопределённые символы»

Признаки в условии

  • к маске и делимости добавлено условие на число: точный квадрат, простое, число делителей
  • символ маски переопределён: например «? — любая чётная цифра»

Идея

Доп. условие дописываем в if (функции is_prime, num_div — из каркаса). Для переопределённого ? штатный fnmatch не годится — переходим на re.fullmatch с классами символов.

Маска + доп. условие (простое частное)

from fnmatch import fnmatch
m = 1917
for x in range(m, 10**10 + 1, m):
    if fnmatch(str(x), '3?12?14*5') and is_prime(x // m):
        print(x, x // m)

regex? — чётная цифра

import re
# ? → [02468], * → \d*
pat = r'3[02468]12[02468]14\d*5'
for x in range(m, 10**10 + 1, m):
    if re.fullmatch(pat, str(x)):
        print(x, x // m)

Ловушки

  • Для переопределённого ? (например, только чётная цифра) fnmatch даст неверный результат — используй re.fullmatch с классом [02468].
  • В регулярках спецсимволы экранируй: \d, \., \+. Маску всегда привязывай целиком через re.fullmatch (или ^…$).
  • Если делимости в условии нет, перебирай структуру (квадраты k*k и т.п.), а не все числа подряд.

Тренировка

Задача 13 — маска с чётным символом

Маска ?7?, где каждый ? — ровно одна чётная цифра. Найдите все числа ≤ 500, соответствующие маске и делящиеся на 6; выведите числа и частные.

Показать ответСкрыть ответ
re.fullmatch(r'[02468]7[02468]', str(x)) по range(6, 501, 6), печать x, x // 6: 270 45
276 46
474 79
похожая с ЕГЭ →
Десять разделов держатся на одном каркасе. Семейство делителей (01–07) это перебор отрезка плюс одна из функций divisors / factorize / is_prime; маски (08–09) — перебор по кратным и fnmatch / regex. Все ответы в тренировке посчитаны и проверены на Python. Пиши код по каркасу, проверь на примере из условия, затем запусти на данных задачи и сверь ответ на тренажёре SilverTests.
Печать