Алгоритмы проверки простых чисел

Проверка простоты – это задача установления, имеет ли натуральное число n ≥ 2 нетривиальные делители. Формально, число n простое, если множества делителей D(n) = { d ∈ ℕ : d | n } содержат ровно два элемента – 1 и n. В вычислительном плане проверка простоты – фундаментальная процедура для криптографии, комбинаторики, теории чисел и олимпиадного/экзаменационного программирования. Для ЕГЭ по информатике эта тема напрямую связывает арифметику остатков, анализ алгоритмов, циклы и ветвления, работу с массивами (решето), а также логические доказательства корректности (инварианты и границы перебора).

Ниже представлены: строгая формализация, правила корректности и безопасной реализации, классификация алгоритмов (детерминированные, вероятностные, решёта), оптимизационные приёмы (ограничение диапазона, колёса делителей, ускоренная модульная степень), мини-шпаргалка формул, типичные ошибки и 5 упражнений в стиле ЕГЭ с подробными решениями.

Формальная модель и базовые факты

1. Определения и эквивалентности
   

   Число n ≥ 2 простое ⇔ не существует d такое, что 1 < d < n и d | n. Эквивалентная и практически важная формулировка:

   n – составное ⇔ ∃ d : 2 ≤ d ≤ ⌊√n⌋ и d | n.

   Отсюда минимально корректный алгоритм: достаточно проверять делители до ⌊√n⌋. Доказательство: если n = ab и a > √n, тогда b < √n.

2. Теорема Ферма и предикаты простоты
   

   Если p – простое и a – целое, взаимно простое с p, то выполняется

   a^{p-1} ≡ 1 (mod p).

   Поэтому для простого p и любого 1 < a < p: a^{p-1} mod p = 1. Обратное неверно (есть числа Кармайкла), но это даёт вероятностные тесты.

3. Представление n-1 = 2^s · d
   

   Для нечётного n > 2 удобно разложить n-1 на степенную двойку:

   n - 1 = 2^s · d,   d – нечётное.

   Это ядро теста Миллера–Рабина (MR): проверка цепочки квадратов a^d, a^{2d}, a^{4d}, …, a^{2^{s-1}d} (mod n).

Классификация алгоритмов

1. Детерминированные переборные методы
   

   1. Тривиальная проверка делителей: тестировать d = 2..⌊√n⌋. Сложность O(√n).

   2. С пропуском чётных: проверить 2, потом d = 3,5,7,… – вдвое быстрее.

   3. Колесо делителей (wheel factorization): тестировать только d, взаимно простые с первым набором малых простых (напр. колёсо по 2·3·5 = 30 → остатки 1,7,11,13,17,19,23,29).

   4. Детерминированные MR для ограниченных диапазонов: для 32-/64-битных чисел известны конечные наборы оснований, делающие MR детерминированным (см. §4.4).

2. Вероятностные тесты
   

   1. Ферма (простые свидетели): случайный a из [2..n-2], проверить a^{n-1} ≡ 1 (mod n). Быстр, но уязвим к числам Кармайкла.

   2. Миллер–Рабин (strong pseudoprime test): значительно надёжнее; вероятность ложноположительного результата не более 1/4 на случайное основание (на практике сильно меньше). Для фиксированного набора оснований ≈ детерминирован для машинных слов.

3. Решёта (массовая простота на диапазоне)
   

   1. Решето Эратосфена: O(n log log n) времени, O(n) памяти; порождает все простые ≤ n.

   2. Сегментированное решето: экономит память, обрабатывая отрезки [L; R] с базовыми простыми ≤ √R.

   3. Линейное решето (Эратосфен–Эйлер): выдаёт простые и минимальные простые делители за O(n) амортизированно.

Правила корректности и инженерные соглашения

1. Границы перебора: никогда не тестируйте делители свыше ⌊√n⌋.

2. Быстрые отсеки: отдельная обработка n < 2, n = 2, n чётное.

3. Модульная степень: реализуйте бинарное возведение в степень:
   

   pow_mod(a, e, m):

     res := 1; x := a mod m

     while e > 0:

       if e & 1 = 1: res := (res · x) mod m

       x := (x · x) mod m

       e := e >> 1

     return res

4. Безопасность умножения: для языков с переполнением используйте 128-битные расширения, монтгомери-умножение или «умножение через сложение по модулю». В Python больших целых достаточно.

5. MR-инварианты: если для основания a не выполнено ни a^d ≡ 1 (mod n), ни a^{2^r d} ≡ -1 (mod n) для некоторого 0 ≤ r < s, то n – составное.

6. Тест Ферма используйте только как фильтр перед MR/перебором.

7. Решёта: помните про начальную маркировку с p^2 и шаг +p.

8. Повторное тестирование: в вероятностных тестах используйте несколько независимых оснований; ошибки падают геометрически.

9. Композитный отбор: проверка делимости на малые простые до 1–2 тысяч ускоряет MR.

10. Идемпотентность кода: функция is_prime(n) не должна иметь побочных эффектов (нужно для безопасного переиспользования в задачах ЕГЭ).

Ключевые алгоритмы (псевдокод и комментарии)

1. Проверка делителей до √n (с «колесом» 2·3·5)
   

   function is_prime_trial(n):

     if n < 2: return false

     for p in [2,3,5]:

       if n = p: return true

       if n % p = 0: return false

     # шаблон остатков по 30: 1,7,11,13,17,19,23,29

     i := 7; step := [4,2,4,2,4,6,2,6]  # циклически

     k := 0

     while i*i ≤ n:

       if n % i = 0: return false

       i := i + step[k]; k := (k + 1) mod 8

     return true

   Сложность: O(√n / log log n) эмпирически быстрее простой нечётной сетки.

2. Быстрое возведение в степень по модулю (бинарный метод)
   

   function pow_mod(a, e, m):

     a := a % m

     res := 1

     while e > 0:

       if (e & 1) = 1:

         res := (res * a) % m

       a := (a * a) % m

       e := e >> 1

     return res

   Сложность: O(log e) умножений по модулю.

3. Миллер–Рабин (одно основание)
   

   function miller_rabin_single(n, a):

     if n % a = 0: return n = a

     d := n - 1; s := 0

     while (d & 1) = 0:

       d := d >> 1

       s := s + 1

     x := pow_mod(a, d, n)

     if x = 1 or x = n - 1: return true

     for r in 1 .. s-1:

       x := (x * x) % n

       if x = n - 1: return true

     return false
   

   Составность при false – доказана; true – «вероятно простое» (или простое).

4. Практический детерминизм для 32/64-бит
   

   Для 32-битных n < 2^32 достаточно оснований {2, 7, 61}.
   Для 64-битных n < 2^64 используются небольшие фиксированные наборы оснований (например, {2, 3, 5, 7, 11, 13, 17} или короче в версиях из литературы). На практике этого достаточно, чтобы MR был детерминированным для машинных целых.

5. Решето Эратосфена (базовый)
   

   function sieve(n):

     is_prime := array[0..n] of true

     is_prime[0] := false; is_prime[1] := false

     for p in 2 .. ⌊√n⌋:

       if is_prime[p]:

         for x in p*p .. n step p:

           is_prime[x] := false

     return is_prime

   Память O(n). Для больших диапазонов – сегментированное решето: храним простые ≤ √R, помечаем кратные в текущем сегменте [L; R].

Мини-шпаргалка (формулы и факты)

1. Граница перебора:
   n составное ⇒ ∃ d : 2 ≤ d ≤ ⌊√n⌋, d | n.

2. Ферма:
   a^{p-1} ≡ 1 (mod p),  если gcd(a, p) = 1 и p – простое.

3. Разложение n − 1:
   n − 1 = 2^s · d, d нечётное → цепочка квадратов в MR.

4. Сложность:
   

   Trial division  – O(√n)

   Sieve           – O(n log log n)

   Pow_mod         – O(log n)

   MR (k основ.)   – O(k log^3 n) при «наивном» умножении; на практике быстрее.

5. Детерминированные основания (практика):
   

   n < 2^32  → a ∈ {2,7,61}  достаточно

   n < 2^64  → a ∈ {2,3,5,7,11,13,17}  (один из безопасных наборов)

Типичные ошибки и профилактика

• Забыли обрабатывать n < 2 → ложные «простые». Исправление: ранние возвраты.
• Переполнение при умножении по модулю → неверные остатки. Исправление: большие типы/безопасные множители/язык с BigInt.
• Проверка делителей дальше √n → лишние итерации. Исправление: стоп-условие по i*i ≤ n.
• Тест Ферма без MR → ложно положительные на Кармайкла. Исправление: MR/доп. основания.
• Маркировка решета с 2p вместо p^2 → лишняя работа. Исправление: стартовать с p*p.
• Отсутствие предварительного отсева малыми простыми → MR грузится на тривиальных композитах. Исправление: деление на малые p ≤ 1000 перед MR.

Связь с подготовкой к ЕГЭ

• Циклы/ветвления: реализация перебора и решёт.
• Арифметика остатков: возведение в степень по модулю, свойства делимости.
• Оценка сложности: сравнение O(√n) vs O(log n) шагов MR.
• Массивы/строки: представление флагов простоты, сегментация.
• Логика/доказательства: доведение границы √n, инварианты решета, корректность MR-ветвлений.

Пять упражнений 

Упражнение 1. Граница √n и число проверок
Условие. Сколько делителей максимум проверит алгоритм перебора делителей (только нечётные после проверки 2) для числа n = 10^10 + 3? Дайте точную формулу и численную оценку.
Решение. Проверяем d = 3,5,7,…, ⌊√n⌋.

⌊√(10^10 + 3)⌋ = ⌊100000√(1 + 3·10^{-10})⌋ = 100000

Чётные пропущены, значит количество кандидатов:

count = ⌈(100000 - 1)/2⌉ = 49999

Плюс проверка на делимость на 2 = 1 операция.
Ответ. ~50 тысяч делителей (точно 49 999 нечётных + проверка на 2).

Упражнение 2. Быстрая степень по модулю
Условие. Вычислите a^{e} mod m для a = 7, e = 560, m = 561. Объясните, почему в тесте Ферма ответ «1» не означает простоту m.
Решение. 561 = 3·11·17 – число Кармайкла, для всех gcd(a,561)=1 выполняется a^{560} ≡ 1 (mod 561). Следовательно,

7^{560} mod 561 = 1

Тем не менее 561 составное (разложение выше).
Вывод. Тест Ферма даёт ложноположительные ответы на числах Кармайкла; нужен MR.

Упражнение 3. Один раунд Миллера–Рабина
Условие. Проверьте число n = 341 (известно: 341 = 11·31) одним раундом MR с основанием a = 2.

1. Найдите s, d такие, что n − 1 = 2^s · d.
2. Проверьте условия MR.

Решение.

1. 1.     n − 1 = 340 = 2^2 · 85, значит s = 2, d = 85.
2. Считаем x = 2^{85} mod 341. Известный факт (или быстрое вычисление) даёт x ≡ 32 (mod 341), не равно 1 и −1 ≡ 340. Квадратируем: x := x^2 mod 341 ≡ 32^2 = 1024 ≡ 1024 − 3·341 = 1024 − 1023 = 1. Ни на первом шаге, ни на втором x не стал −1; получился 1 раньше −1, что по правилу MR означает составность.
   Ответ. Тест Миллера–Рабина с a=2 объявляет 341 составным.

Упражнение 4. Решето на диапазоне и количество пометок
Условие. В базовом решете до n = 100 сколько присваиваний is_prime[x] := false произойдёт при внешнем цикле p? Ответ дайте как сумму по всем простым p ≤ 10 (поскольку ⌊√100⌋ = 10).
Решение. Пометки идут от p^2 до 100 шагом p. Число пометок для данного p:

cnt(p) = ⌊(100 - p^2)/p⌋ + 1,  если p^2 ≤ 100; иначе 0.

Простые ≤ 10: 2,3,5,7.

• p=2: p^2=4 → cnt=⌊(100-4)/2⌋+1=⌊96/2⌋+1=48+1=49
• p=3: p^2=9 → cnt=⌊(100-9)/3⌋+1=⌊91/3⌋+1=30+1=31
• p=5: p^2=25 → cnt=⌊(100-25)/5⌋+1=⌊75/5⌋+1=15+1=16
• p=7: p^2=49 → cnt=⌊(100-49)/7⌋+1=⌊51/7⌋+1=7+1=8
  Сумма: 49+31+16+8 = 104.
  Ответ. 104 пометки false.

Упражнение 5. Сравнение сложностей: перебор vs MR
Условие. Оцените, при каких порядках величин n выгодно заменить перебор делителей на MR с 3 основаниями, если умножение по модулю выполняется за O(1) (условно, за счёт больших типов), а стоимость одной проверки делителя – O(1). Дайте асимптотическое сравнение.
Решение.

Перебор: T_trial(n) ≈ c₁ · √n.

MR: один раунд – O(log n) умножений; три раунда – T_MR(n) ≈ c₂ · 3 log n.
Сравниваем √n и log n: асимптотически

√n ≫ log n   (при n → ∞)

т.е. MR выгоден уже при умеренных n (на практике – начиная с n в несколько тысяч/десятков тысяч и выше, в зависимости от констант, языка и железа).
Ответ. Асимптотически MR предпочтительнее; практический порог – «тысячи+».

Практические рекомендации по реализации для задач ЕГЭ

• Быстрый фильтр: проверьте делимость на малые простые 2..97, затем MR (2–3 основания) – почти мгновенно отсеивает композиты.
• Типы данных: если язык без BigInt – аккуратнее с переполнением в pow_mod.
• Тестирование: обязательно покройте n = 0,1,2,3, чётные, квадраты простых (частая ловушка).
• Решето: для «много чисел до N» всегда лучше порождать таблицу простых и переиспользовать.
• Стиль: функция is_prime – чистая, без print внутри; на выход – булево.

Чек-лист самопроверки

• Обработаны случаи n < 2, n ∈ {2,3}, n чётное.
• В переборе стоп-условие i*i ≤ n.
• pow_mod реализован бинарно, проверен на краях.
• Для MR корректно найдено s, d и реализована цепочка квадратов.
• Используется отбор малыми простыми до MR.
• Для диапазона – применено решето (при необходимости сегментируется).
• Проанализирована сложность и даны обоснованные границы.

Контрольные вопросы

1. Почему достаточно проверять делители до ⌊√n⌋?
2. В чём принципиальная разница между тестами Ферма и Миллера–Рабина?
3. Зачем в MR раскладывать n − 1 как 2^s · d?
4. Где в решете начинается маркировка и почему шаг равен p?
5. Почему добавление отбора малыми простыми перед MR ускоряет общий алгоритм?

Заключение

Алгоритмы проверки простоты опираются на чёткие математические инварианты (граница √n, малые теоремы о модулярной арифметике) и аккуратную инженерную реализацию (быстрая модульная степень, безопасное умножение, корректная цепочка MR). Для единичных чисел и малых диапазонов достаточно оптимизированного перебора; для больших
значений – выигрывают вероятностные тесты с детерминированными наборами оснований. Для ЕГЭ эти подходы тренируют аналитику сложности, владение циклами и условиями, уверенную работу с остатками и массивами, а также корректное оформление кода и доказательств.