Как решать задание 25 ЕГЭ по информатике — обработка целочисленной информации

О чём задание 25

Задание 25 — работа с целыми числами. Типовая формулировка: «найди все натуральные числа из диапазона [A, B], у которых есть такое-то свойство, и выведи их по правилу из условия». Или: «выведи первые N чисел, упорядоченных по определённому критерию».

Задание стоит 1 первичный балл. В КЕГЭ 2026 это последнее одноочковое задание — дальше идут только двухочковые 26 и 27, которые проверяют программирование и анализ данных. Стабильно сдавать 25-е — обязательное условие для 70+ тестовых баллов. Подготовку с нуля мы разбирали в отдельной статье.

Типовые свойства

Свойство	Как проверять
Простое число	Перебор делителей до sqrt(n)
Наибольший простой делитель	Последовательное деление на простые
Сумма делителей равна S	Перебор делителей с парой n/d
Количество делителей равно k	Подсчёт в цикле до sqrt(n)
Сумма цифр равна S	sum(int(d) for d in str(n))
Палиндром	str(n) == str(n)[::-1]
Цифровой корень равен r	Повторная сумма цифр до одной цифры
Кратность / делимость	n % k == 0

Смешанные условия — тоже частые: «найди числа, у которых НПД равен 5 и сумма цифр чётная». Решение — два флага в теле цикла.

Базовые шаблоны

Простое число

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True          # 2 и 3
    if n % 2 == 0:
        return False
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2               # только нечётные делители
    return True

Две оптимизации:

1. Сразу отсекаем 2, потом идём по нечётным — вдвое меньше итераций.
2. Условие d * d <= n, а не d <= sqrt(n) — без вызова sqrt, чуть быстрее.

Наибольший простой делитель

def largest_prime_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            n //= d
        else:
            d += 1
    return n

Алгоритм: делим n на 2 столько раз, сколько можем, потом на 3, на 5 и так далее. В переменной n в конце остаётся либо 1, либо самый большой простой делитель. Единственное тонкое место — если исходное n простое, функция вернёт исходное число.

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

def sum_divisors(n):
    total = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            total += d
            if d != n // d:     # не добавлять sqrt(n) дважды для полного квадрата
                total += n // d
        d += 1
    return total

Классика: делители ходят парами. Если n = 36, d = 6, то n/d = 6 — тот же делитель, его не нужно добавлять дважды. Проверка d != n // d это ловит.

Сумма цифр и палиндром

def sum_digits(n):
    return sum(int(ch) for ch in str(n))

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

Строковые операции в ЕГЭ разрешены и работают быстро. Писать руками через % 10 и // 10 не обязательно — кода больше, смысла меньше.

Полный пример: числа со свойством

Условие: «найди все натуральные числа x из диапазона [A, B], для которых наибольший простой делитель меньше самого числа (то есть x — составное). Выведи их в порядке возрастания по одному в строке, рядом — значение наибольшего простого делителя».

def largest_prime_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            n //= d
        else:
            d += 1
    return n

A = 174457
B = 174505

for x in range(A, B + 1):
    lpf = largest_prime_factor(x)
    if lpf < x:
        print(x, lpf)

Простые числа исключаются автоматически — у простого x функция вернёт само x, и условие lpf < x не выполнится.

Оптимизация: не вызывать функцию дважды

В коде выше largest_prime_factor(x) вызывается один раз — результат сохранён в lpf. Плохой вариант выглядит так:

if largest_prime_factor(x) < x:
    print(x, largest_prime_factor(x))   # повторный вызов — вдвое медленнее

На больших диапазонах второй вызов может удвоить время выполнения. Всегда сохраняй результат в переменную, если используешь его дважды.

Разобранная задача 1: простые числа в диапазоне

Найди все простые числа в диапазоне [100 000; 100 500] и выведи их сумму.

Решение

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

A, B = 100000, 100500
total = sum(x for x in range(A, B + 1) if is_prime(x))
print(total)

Тайминг

500 проверок, каждая до sqrt(100000) ≈ 316 итераций — около 150 000 операций. Работает меньше секунды даже в онлайн-интерпретаторе.

Альтернатива — решето

Для огромных диапазонов (миллионы чисел) используется решето Эратосфена. Но на ЕГЭ это избыточно: диапазоны обычно до 10^6 чисел, и прямая проверка простоты проходит за секунды.

Типичная ошибка

if n % 2 == 0:
    return False      # ловушка: для n = 2 вернёт False, хотя 2 — простое

В коде выше пропущен случай n == 2. Исправленный вариант — return n == 2. Всегда проверяй функцию на маленьких значениях: 0, 1, 2, 3.

Разобранная задача 2: числа с наибольшим простым делителем в диапазоне

Найди все натуральные числа x в диапазоне [1 000 000; 1 100 000], у которых наибольший простой делитель меньше 100. Выведи их количество и сумму.

Разбор

Задача сложнее: диапазон — 100 000 чисел, для каждого нужна факторизация. Простая реализация с факторизацией O(sqrt(n)) на число даёт 100000 × 1000 = 10^8 операций — на грани 5-секундного лимита Python.

Оптимизация 1: ранний выход

def has_large_prime_factor_ge(n, limit):
    """True, если у n есть простой делитель >= limit."""
    d = 2
    while d * d <= n:
        if n % d == 0:
            if d >= limit:
                return True
            n //= d
        else:
            d += 1
    return n >= limit      # остаток — либо 1, либо простое число

Как только нашли делитель >= limit — сразу True, не тратим время.

Оптимизация 2: пропуск чётных после двойки

def largest_prime_factor(n):
    result = 1
    while n % 2 == 0:
        result = 2
        n //= 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            result = d
            n //= d
        else:
            d += 2
    if n > 1:
        result = n
    return result

После отсечения двоек делители могут быть только нечётными — шаг d += 2.

Полное решение

def largest_prime_factor(n):
    result = 1
    while n % 2 == 0:
        result = 2
        n //= 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            result = d
            n //= d
        else:
            d += 2
    if n > 1:
        result = n
    return result

A, B = 1_000_000, 1_100_000
count = 0
total = 0
for x in range(A, B + 1):
    if largest_prime_factor(x) < 100:
        count += 1
        total += x

print(count, total)

Тайминг

После оптимизаций — около 2-3 секунд на обычном ноутбуке. Приемлемо для ЕГЭ.

Типичная ошибка: TLE

Наивная реализация «перебирай делители от 2 до n» даёт сложность O(n) на число. На миллионе чисел это 10^12 операций — не пройдёт никогда. Всегда используй d * d <= n, а не d <= n.

Одним циклом vs предвычисления

Для многих задач помогает предвычислить таблицу. Например, если нужна сумма цифр каждого числа из большого диапазона — считать её на лету быстрее, чем заранее. А вот если нужен наибольший простой делитель всех чисел до N — решето с минимальным простым делителем даёт O(N log log N):

N = 1_000_000
min_prime = list(range(N + 1))   # min_prime[i] — наименьший простой делитель i
for i in range(2, N + 1):
    if min_prime[i] == i:        # i — простое
        for j in range(i * i, N + 1, i):
            if min_prime[j] == j:
                min_prime[j] = i

def largest_prime_factor_fast(n):
    lpf = 1
    while n > 1:
        lpf = min_prime[n] if min_prime[n] == n else 1  # упрощено для иллюстрации
        p = min_prime[n]
        while n % p == 0:
            n //= p
        lpf = p if n == 1 else lpf
    return lpf

На ЕГЭ это редко нужно, но полезно знать: если решение в лоб не укладывается в 5 секунд — иди в сторону предвычислений.

Тайминг и стратегия

В КЕГЭ на 27 заданий даётся 235 минут. Рекомендуемое распределение для 25-го задания:

• 2-3 минуты — прочитать условие, выписать свойство и формат вывода.
• 5 минут — вспомнить нужный шаблон (простое, делители, сумма цифр и т.д.).
• 5-8 минут — написать код, проверить на мелком примере.
• 1-2 минуты — запустить на полном диапазоне, скопировать ответ.
• 1 минута — перепроверить формат вывода.

Итого — 15-20 минут. Если не получилось за 25 — пропускай и возвращайся в конце. Терять 40 минут на 1 балл — плохая стратегия, когда впереди двухочковые 26 и 27.

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

Ошибка	К чему ведёт	Как исправить
Перебор делителей до n, а не до sqrt(n)	TLE на больших диапазонах	Условие d * d <= n в цикле
Пропуск n == 2 в проверке простоты	2 не попадает в простые	Отдельно обработать n < 4
Повторный вызов функции в print	Удвоение времени	Сохрани результат в переменную
Неверный порядок вывода	Ноль за задание	Перечитать условие 2 раза
Забытая сортировка	Ответ в случайном порядке	Всегда проверяй sorted() перед выводом
Добавление sqrt(n) дважды в сумме делителей	Неверный ответ для полного квадрата	Проверка d != n // d
Путаница делителей и простых делителей	Свойство проверяется не то	В функции НПД после цикла проверь остаток n

Особенно коварная ошибка

Граница диапазона. Условие «числа из диапазона [A; B]» означает включительно оба конца. В Python: range(A, B + 1). Забудешь +1 — потеряешь последнее число в ответе. Проверяй на мелком примере: range(5, 10) даёт [5, 6, 7, 8, 9], а не [5, 6, 7, 8, 9, 10].

Как тренироваться

1. Выучи 5 шаблонов наизусть: простое число, НПД, сумма делителей, сумма цифр, палиндром. Каждый пиши с нуля без подглядывания.
2. Решай по типам: 3-5 задач на каждое свойство подряд, чтобы закрепить.
3. Проверяй на малых значениях: запускай функцию на n=0, 1, 2, 3, 10, 100 — и сверяй ответ руками.
4. Тренируй тайминг: засекай время. Цель — 15 минут на задачу средней сложности.

Полезные материалы:

• Задание 2 ЕГЭ по информатике — ещё одна задача с перебором
• Задание 6 ЕГЭ по информатике — алгоритмы и исполнители
• Задание 24 ЕГЭ по информатике — предыдущее задание про строки
• Задание 27 ЕГЭ по информатике — финальное задание на программирование
• Python или C++ для ЕГЭ — какой язык выбрать для программирования
• Python-идиомы для ЕГЭ — короткие приёмы на все задачи

Выводы

• Задание 25 — последнее одноочковое, обязательно сдаваемое при подготовке к 70+ тестовым.
• Главная оптимизация — перебор делителей до sqrt(n). Без неё большие диапазоны не пройдут по времени.
• Алгоритм наибольшего простого делителя — деление на простые с шагом по возрастанию. 10 строк кода, которые решают половину задач.
• Не вызывай функцию дважды, всегда сохраняй результат. Сортируй вывод, если нужно.
• Если после 20 минут не решил — пропусти. 25-е — всего 1 балл из 29, а впереди 26 и 27.

На экзамене задание 25 — это проверка того, что ты знаешь стандартные шаблоны и умеешь их быстро адаптировать. Выучи 5 шаблонов, и 95% условий будут решаться за 15 минут.