Во всех функциях ниже нам нужно вычислить целую часть квадратного корня — предельную границу перебора делителей. Есть два способа:

Способ 1 — через float: int(n**0.5). Сначала Python возводит n в степень 0.5 (получается число с плавающей точкой float), затем откусывает дробную часть через int.

Способ 2 — через целочисленную функцию: isqrt(n) из модуля math. Эта функция работает без вычислений с плавающей точкой: она сразу ищет максимальное целое k, для которого k² ≤ n, используя целочисленный алгоритм.

В чём разница на практике? Тип float в Python (это стандарт IEEE 754 двойной точности) хранит около 15–16 значащих десятичных цифр. Для чисел больше 10¹⁵ округления уже дают о себе знать. Возьмём конкретное число:

Разница в единицу — казалось бы мелочь, но если цикл идёт for d in range(2, int(n**0.5) + 1), лишняя итерация может или пропустить корневой делитель, или наоборот заглянуть за границу — оба варианта дают неверный ответ.

Второе преимущество isqrt — скорость. Целочисленный алгоритм в C-реализации быстрее, чем вычисление **0.5 через плавающую точку плюс приведение к int. На миллионе вызовов разница ощутима.

Третье — корректная граница. При переборе делителей нужен диапазон range(1, isqrt(n) + 1): символ +1 стоит потому, что range не включает правую границу, а нам нужно дойти до самого isqrt(n).

Самая используемая функция в задании 25. Возвращает отсортированный список всех натуральных делителей числа n — от 1 до самого n.

Принцип работы разобран в §01: делители ходят парами, один из пары всегда не превосходит √n. Значит достаточно пробежать d от 1 до isqrt(n) и на каждом совпадении добавить оба делителя. Чтобы не получить дубликат при n = k² (когда d = n // d), используем set — он автоматически отбросит повтор.

Что возвращает и как использовать:

Срез divs(n)[1:-1] — чистый и короткий способ получить нетривиальные делители (без 1 и без самого n). Для простых n возвращает пустой список — удобно для проверок.

Проверяет, является ли число n простым. Возвращает True или False. В задании 25 используется всюду, где фигурируют «простые множители» — блоки §03, §04.

Логика такая: число простое, если у него нет делителей от 2 до √n. Как только нашли хотя бы один — сразу возвращаем False. Если дошли до конца цикла без совпадений — значит число простое, возвращаем True.

Оптимизация: после проверки делимости на 2 шагаем по нечётным числам (с шагом 2). Это вдвое ускоряет функцию без потери корректности — если n не делится на 2, оно точно не делится на 4, 6, 8...

Для диапазона ЕГЭ (n до 10¹⁰) функция отрабатывает за ~100 000 итераций в худшем случае — миллисекунды. Если понадобится проверять простоту тысяч чисел в одном цикле — лучше использовать решето (Функция 3).

Когда задача требует не проверить одно число, а получить список всех простых до некоторой границы N — решето Эратосфена на порядки быстрее, чем вызывать is_prime для каждого числа по отдельности.

Идея: создаём массив флагов длины N+1, где sieve[i] означает «число i — простое?». Изначально все единицы, кроме sieve[0] и sieve[1]. Затем для каждого простого p зачёркиваем все его кратные: 2p, 3p, 4p, .... В конце единицы в массиве стоят только на простых позициях.

Для хранения флагов используем bytearray — встроенный тип Python (как list или str, импорты не нужны, на ЕГЭ абсолютно легален). bytearray хранит байты, поэтому занимает в 8 раз меньше памяти, чем list из целых чисел. Для N = 10⁷ это разница между 10 МБ и 80 МБ — критично на ЕГЭ, где ограничения на память жёсткие.

Главная тонкость: начинаем зачёркивание с p*p, а не с 2p. Все числа 2p, 3p, ..., (p-1)·p уже были зачёркнуты ранее — при обработке простых меньше p. Первое «новое» кратное, которое ещё не тронуто, — это p·p. Поэтому внешний цикл идёт только до isqrt(N): если p > isqrt(N), то p² > N и вычёркивать нечего.

Строка a[p*p :: p] = bytearray(len(a[p*p :: p])) обнуляет сразу все кратные p, начиная с p². Эта идиома выглядит непривычно — её подробный разбор в следующей секции.

На каких размерах N имеет смысл звать sieve? Для N ≤ 10⁷ — точно, отработает за пару секунд и съест ~10 МБ. Для N = 10⁸ — уже на грани, 100 МБ может не хватить. Если задача просит простые в диапазоне до 10⁹, решето не подходит — лучше использовать is_prime для отдельных чисел.

Самая непонятная строка в sieve — это a[p*p :: p] = bytearray(len(a[p*p :: p])). За одну операцию она обнуляет все элементы массива с индексами p², p²+p, p²+2p, … — то есть все кратные p, начиная с p². Разберём по кусочкам.

Возьмём крошечный пример для наглядности: a = bytearray([1] * 20) — массив из 20 единичек с индексами от 0 до 19. И пусть p = 3. Тогда p*p = 9, и мы хотим обнулить a[9], a[12], a[15], a[18] — все кратные 3, начиная с 9.

В применении к решету Эратосфена: если p = 3 и N = 20, то после этой строки все числа 9, 12, 15, 18 помечены как составные. Внешний цикл перейдёт к следующему простому (p = 5), и снова одной строкой обнулит a[25], a[30], ... — и так далее.

Почему не написать проще — через обычный цикл? Сравним два варианта:

Оба варианта дают абсолютно одинаковый результат. Но вариант B работает в 10–20 раз быстрее. Причина проста.

В варианте A на каждую итерацию Python выполняет десятки внутренних операций: проверка условия цикла, вычисление следующего k, вызов a.__setitem__, инкремент счётчика. Всё это — шаги интерпретатора. Для N = 10⁷ и простого p = 2 нужно пройти 5 миллионов итераций. Добавьте сюда все остальные простые — получите десятки миллионов медленных операций.

В варианте B присваивание в срез обрабатывается одной функцией на уровне C: она напрямую пишет нули в память массива, без возврата в интерпретатор Python между элементами. Для того же N = 10⁷ вся операция занимает десятые доли секунды.

Почему вообще срез-идиома эффективна именно для bytearray, а не для list? Потому что bytearray хранит байты непрерывно в памяти (как массив в C), и CPython умеет копировать в него байты блоками через memmove. У list внутри — массив указателей на Python-объекты, и массовое присваивание там медленнее.

Итого: bytearray + срез-идиома — это не просто «короче написать», а принципиально более быстрый способ работы с массивом флагов. Для задания 25 запоминаем именно эту пару.

Раскладывает n на простые множители с учётом кратности. Возвращает список простых, где каждое простое повторяется столько раз, сколько оно входит в разложение.

Нужна в задачах, где требуется узнать структуру числа: «состоит из двух различных простых», «является степенью простого», «имеет три простых множителя». В §03 мы делали факторизацию через цикл с первым делителем — функция factor делает то же самое в общем виде.

Алгоритм: идём d от 2 и «откусываем» от n все вхождения d (в цикле while n % d == 0, добавляя d в список и деля n на d). Когда d*d > n, цикл заканчивается. Если после цикла n > 1 — остаток сам является простым и добавляется в список.

Обратите внимание: factor возвращает множители с повторами. Чтобы получить уникальные простые — применяем set(factor(n)). Чтобы получить разложение в виде «простое → степень» — можно использовать collections.Counter, но для школьной задачи обычно достаточно factor + set.

Эта таблица — главное, ради чего написан параграф. Запоминаем один раз — применяем на любой задаче 25.

Храните эти 30 строк в готовом виде. На экзамене вставляете в начало программы, дальше используете любую комбинацию функций под условие конкретной задачи.