ЕГЭ по информатике · паттерны
Задание 25
Один универсальный каркас и небольшая библиотека функций — делители, факторизация, простые числа, маски, — которые закрывают практически любую формулировку задания за 2021–2026 годы. Сначала каркас, затем восемь типов как его настройки.
1 первичный баллрешения на Pythonуниверсальный каркас9 разделовпроверенные ответы
00
Универсальный каркас
«Два скелета и одна библиотека — всё остальное это их настройка»
Любое задание 25 распадается на две схемы. Если в условии есть маска (символы ? и *) — работает каркас Б (перебор по кратным). Во всех остальных случаях — каркас А (перебор отрезка + характеристика числа + фильтр). Дальше меняются только функция-характеристика, условие и то, что выводим.
Библиотека (вставляй нужные функции в начало)
Как читать условие — выбор каркаса и функции
- В условии есть маска (
?, *) и делимость на m? → каркас Б (разделы 08–09).
- Нужны все делители (количество, сумма, наибольший, делитель со свойством)? →
divisors() (разделы 01, 02, 05, 07).
- Речь о простых множителях, их количестве, степенях, или о числе делителей формулой? →
factorize() / num_div() (разделы 03, 06).
- Надо проверить простоту или найти простые на отрезке / с номером? →
is_prime() или решето (раздел 04).
- Последний шаг всегда один: вывести ровно те поля и в том порядке, что просит условие.
Три ошибки, общие для всех типов
- Что исключать. «Не считая 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
похожая с ЕГЭ →