Задание № 25 ЕГЭ по информатике проверяет умение писать алгоритмы для обработки целых чисел и работать с перебором. В статье разберём три основных типа задач 2026 года:
- поиск делителей числа с различными условиями (сумма, количество, свойства);
- перебор чисел по маске с использованием модуля fnmatch;
- проверка простых чисел и их свойств (например, разность между соседними простыми числами).
Термины, которые будем использовать: делитель, простое число, оптимизация, маска числа.
Задачи на делители числа
Делители числа удобно искать парами: если a — делитель n, то n//a — тоже делитель. Это позволяет перебирать значения только до $\sqrt{n}$.
Основной алгоритм поиска всех делителей:
def find_divisors(n):
divs = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
divs.append(i) # Добавляем i
if i != n // i: # Если i ≠ n//i, добавляем парный делитель
divs.append(n // i)
return sorted(divs)Типовые условия из ЕГЭ
1. Найти минимальный делитель, больший 1 (он же наименьший простой делитель).
def min_divisor(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return i
return n # Если делителей нет, число простое2. Найти сумму минимального и максимального делителей (не считая 1 и n).
def M(n):
divisors = []
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
if not divisors:
return 0
return min(divisors) + max(divisors)Пример из демоверсии
Найти числа, большие 800 000, у которых сумма минимального и максимального делителей (не считая 1 и n) оканчивается на 4.
def M(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return i + n // i
return 0
count = 0
n = 800000
while count < 5:
n += 1
val = M(n)
if val != 0 and val % 10 == 4:
count += 1
print(n, val)Задачи на маски
Второй тип задач — работа с числовыми масками. В них используются специальные символы:
- ? — заменяет ровно одну любую цифру;
- * — обозначает любую последовательность цифр, включая пустую.
Модуль fnmatch
Python предоставляет встроенный модуль fnmatch для работы с такими масками:
from fnmatch import fnmatch
# Проверка, соответствует ли строка маске
if fnmatch(str(number), "3?12?14*5"):
# Число подходит под маскуОсновной алгоритм решения задач с масками
from fnmatch import fnmatch
# Важно: перебираем числа, кратные делителю (это ускоряет перебор в 2026 раз!)
for num in range(2026, 10**10 + 1, 2026):
if fnmatch(str(num), "5?34?71*2"):
print(num, num // 2026)Пример из демоверсии
Найти числа до 10¹⁰, соответствующие маске 3?12?14*5 и делящиеся на 1917.
python
from fnmatch import fnmatch
for num in range(0, 10**10 + 1, 1917):
if fnmatch(str(num), "3?12?14*5"):
print(num, num // 1917)
Задачи на простые числа
Третий тип задач сочетает работу с делителями и проверку чисел на простоту. Рассмотрим алгоритм проверки числа на простоту:
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return TrueПрактикум
Задание 1
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите первые 5 чисел, большие 3 243 000, которые разбиваются на 2 простых множителя, не обязательно различных, которые содержат в себе ровно один 0. В ответе запишите число и сумму делителей.
def pr(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
mas = []
for i in range(3_243_000, 5_000_000):
count = 0
delit = []
for j in range(2, int(i**0.5) + 1):
if i % j == 0:
if pr(j) == True and pr(i//j) == True:
if str(j).count('0') == 1 and str(i//j).count('0') == 1:
count += 2
delit = [j, i//j]
if count >= 2:
mas.append([i, delit[1] + delit[0]])
print(i, delit[1] + delit[0], len(delit))
if len(mas) == 5:
print(mas)
breakОтвет:
3243491 30420
3243601 3602
3243689 8490
3244069 10874
3244133 30426
Задание 2
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите первые 5 чисел, большие 3 243 000, которые разбиваются на 2 простых множителя, не обязательно различных, которые содержат в себе ровно одну цифру 7. В ответе запишите число и сумму делителей.
def pr(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
mas = []
for i in range(3_243_000, 5_000_000):
count = 0
delit = []
for j in range(2, int(i**0.5) + 1):
if i % j == 0:
if pr(j) == True and pr(i//j) == True:
if str(j).count('7') == 1 and str(i//j).count('7') == 1:
count += 2
delit = [j, i//j]
if count >= 2:
mas.append([i, delit[1] + delit[0]])
print(i, delit[1] + delit[0], len(delit))
if len(mas) == 5:
print(mas)
breakОтвет:
3243013 87686
3243073 190786
3243079 463304
3243179 9204
3243199 25664
Задание 3
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите первые 5 чисел, большие 1 468 000, которые разбиваются на 2 простых множителя, не обязательно различных, которые содержат в себе ровно одну цифру 4. В ответе запишите число и сумму делителей.
def pr(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
mas = []
for i in range(1_468_000, 5_000_000):
count = 0
delit = []
for j in range(2, int(i**0.5) + 1):
if i % j == 0:
if pr(j) == True and pr(i//j) == True:
if str(j).count('4') == 1 and str(i//j).count('4') == 1:
count += 2
delit = [j, i//j]
if count >= 2:
mas.append([i, delit[1] + delit[0]])
print(i, delit[1] + delit[0], len(delit))
if len(mas) == 5:
print(mas)
breakОтвет:
1468157 4578
1468417 3838
1468609 31294
1468703 31296
1468751 34200
Заключение
После разбора задания № 25 становится понятно, как подходить к разным типам задач и не теряться в переборе.
Теперь ты умеешь:
- находить делители с учётом оптимизации до $\sqrt{n}$;
- работать с масками и ускорять перебор за счёт кратности;
- проверять числа на простоту и использовать это в составных условиях.
Эти приёмы позволяют уверенно решать типовые задания на делители, маски и простые числа. Дальше важно закрепить их на практике и научиться быстро выбирать подходящий алгоритм под конкретное условие.
Автор статьи
