Предыдущее простое число

Предыдущее Простое Число: Полное Руководство

Задача «найти предыдущее простое число» — зеркальное отражение задачи о следующем простом. Она возникает при работе с делимостью, в криптографии (при подборе модулей), в олимпиадных задачах и в анализе простых пробелов. Внешне всё просто: перебираем числа вниз от N и проверяем каждое на простоту. Но за этой простотой стоят те же глубокие идеи, что и в случае следующего простого: распределение простых чисел, простые пробелы, теорема о среднем расстоянии между простыми. В этой статье мы разберём, что такое предыдущее простое число, как его найти вручную и алгоритмически, какие бывают особые случаи и почему иногда предыдущее простое находится совсем рядом, а иногда — через десятки шагов.

Что Такое Предыдущее Простое Число?

Предыдущее простое число для заданного числа N — это наибольшее простое число, строго меньшее N. Обозначим его p_prev(N). Формально:

Например:

• Предыдущее простое для 10 — это 7.
• Предыдущее простое для 20 — это 19.
• Предыдущее простое для 100 — это 97.
• Предыдущее простое для 1000 — это 997.
• Предыдущее простое для 10007 — это 9973.

Если само число N простое, предыдущее простое — это не оно само, а ближайшее простое строго меньше N. Например, для N = 7 предыдущее простое — 5, а не 7. Для N = 3 предыдущее — 2, а для N = 2 предыдущего простого не существует вовсе.

Как Найти Предыдущее Простое Число

Базовый алгоритм состоит из трёх шагов:

1. Начните с N − 1. Проверьте, является ли это число простым.
2. Если да — это ответ. Если нет — переходите к следующему числу вниз.
3. Повторяйте, пока не найдёте простое.

Проверка каждого кандидата — обычная проверка простоты: перебор делителей от 2 до √N. Если ни один делитель не подошёл, число простое.

Пример: предыдущее простое для 100

Пример: предыдущее простое для 1000

Пример: предыдущее простое для 10007

Простые Пробелы: Разность Между Соседними Простыми

Простой пробел (prime gap) — это разность между двумя последовательными простыми числами. Если p_prev — предыдущее простое для N, а p_next — следующее, то пробелы равны N − p_prev и p_next − N. Обычно они разные, потому что N редко лежит ровно посередине.

Свойства простых пробелов:

• Минимальный пробел — 1, между 2 и 3.
• Пробел 2 — между простыми числами-близнецами: (3, 5), (5, 7), (11, 13), (17, 19).
• Пробел 4 — между «двоюродными» простыми: (7, 11), (13, 17), (19, 23).
• Средний пробел растёт как ln N: чем больше числа, тем реже встречаются простые.
• Большие пробелы существуют: например, между 887 и 907 пробел равен 20, между 9551 и 9587 — 36.

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

Диапазон	Максимальный пробел	Между числами
до 100	8	89 → 97
до 1000	20	887 → 907
до 10 000	36	9551 → 9587
до 100 000	72	31397 → 31469
до 1 000 000	114	492113 → 492227

Как видно из таблицы, предыдущее простое может быть совсем близко (например, на расстоянии 1 или 2) или далеко (десятки единиц). Наш калькулятор показывает точную разность для любого введённого числа.

Алгоритм Поиска Предыдущего Простого Числа

На практике для поиска предыдущего простого используется оптимизированный перебор:

1. Обработайте особые случаи. Если N ≤ 2 — предыдущего простого нет. Если N = 3 — предыдущее простое 2.
2. Начните с N − 1. Если N − 1 чётное, уменьшите его на 1 — так мы сразу пропустим все чётные числа.
3. Проверяйте только нечётные кандидаты. Двигайтесь с шагом 2: N − 1, N − 3, N − 5…
4. Для каждого кандидата выполняйте проверку простоты: перебор делителей до √N.
5. Остановитесь, когда найдёте простое.

Такая оптимизация сокращает перебор вдвое: мы никогда не проверяем чётные числа. Дополнительно можно проверять делимость на 3 и использовать шаг 6k ± 1 — это даёт ещё большее ускорение для больших чисел.

Следующее Простое Число: Симметричная Задача

Обратная задача — найти следующее простое число: наименьшее простое, строго большее N. Алгоритм зеркально симметричен:

1. Если N < 2 — следующее простое 2.
2. Начните с N + 1. Если чётное, увеличьте на 1.
3. Двигайтесь вверх с шагом 2, проверяя простоту каждого кандидата.

Например, следующее простое после 100 — 101 (разность 1), после 1000 — 1009 (разность 9), после 10 000 — 10007 (разность 7).

Пара «предыдущее — следующее» даёт полную картину ближайших простых чисел и помогает оценить простой пробел вокруг введённого числа. Если N — простое, то предыдущее и следующее — это его «соседи» в последовательности простых.

Зачем Нужно Искать Предыдущее Простое Число

• Криптография. При генерации ключей RSA важно знать ближайшие простые по обе стороны от случайного числа — это помогает выбрать оптимальный модуль.
• Хеш-таблицы. Размер хеш-таблицы часто берут равным простому числу, ближайшему к нужному значению. Иногда выгоднее взять предыдущее простое, а не следующее.
• Программирование. Генераторы псевдослучайных чисел используют простые модули, которые выбираются как предыдущее или следующее простое.
• Олимпиадные задачи. Многие задачи на делимость и остатки требуют найти ближайшее простое число в заданном направлении.
• Теория чисел. Исследование простых пробелов — активная область математики, связанная с гипотезой Римана.
• Учебные задачи. Проверка понимания простых чисел и делимости — стандартное упражнение в школьной программе.

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

• Ошибка 1: включать само N, если оно простое. Если N = 7, предыдущее простое — 5, а не 7. Определение требует строгого неравенства p < N.
• Ошибка 2: проверять только чётные числа. После 2 все простые нечётные, поэтому проверять чётные кандидаты бессмысленно — их можно сразу пропускать.
• Ошибка 3: перебирать делители дальше √N. Если делителя не нашлось до √N, его нет вообще. Перебор дальше — пустая трата времени.
• Ошибка 4: считать 1 простым числом. Единица не простое число. Если ввести 3, предыдущее простое — 2, а не 1.
• Ошибка 5: путать предыдущее и следующее. Предыдущее — меньше N, следующее — больше N. Не перепутайте направление.
• Ошибка 6: считать, что пробел всегда маленький. Иногда между соседними простыми числами проходит 30, 50 и даже 100+ единиц.
• Ошибка 7: забыть про особые случаи. Для N = 2 предыдущего простого нет, для N = 3 — это 2. Общий алгоритм нужно дополнять проверками.

Часто Задаваемые Вопросы

Какое предыдущее простое число для 100?
97. Разность равна 3, потому что между 97 и 100 нет простых чисел.

Какое предыдущее простое число для 1000?
997. Разность равна 3.

Какое предыдущее простое число для 10000?
9973. Разность равна 27, потому что 9999, 9998, …, 9974 — все составные или чётные.

Если N простое, предыдущее — это N?
Нет. Предыдущее простое строго меньше N. Например, для N = 7 предыдущее — 5.

Существует ли предыдущее простое для 2?
Нет. 2 — наименьшее простое число. Для N = 2 предыдущего простого не существует.

Всегда ли предыдущее простое находится близко?
В среднем разность растёт как ln N, то есть для N = 10⁶ средний пробел около 14. Но бывают и большие пробелы — до 114 в диапазоне до 10⁶.

Как быстро работает поиск предыдущего простого?
Для чисел до 10¹² поиск занимает доли секунды. Для очень больших чисел нужны вероятностные тесты (Миллера — Рабина).

Можно ли найти предыдущее простое в уме?
Для небольших чисел — да, если помнить таблицу простых чисел и признаки делимости. Для чисел больше 1000 удобнее использовать калькулятор.

Заключение

Поиск предыдущего простого числа — задача, которая дополняет поиск следующего и даёт полную картину ближайших простых. Алгоритм прост: перебираем числа вниз, пропускаем чётные, проверяем простоту. Но за этой простотой стоят важные математические идеи: простые пробелы, оптимизация перебора делителей, теорема о распределении простых чисел. Наш калькулятор выполняет поиск автоматически, показывает предыдущее и следующее простое, вычисляет разности и объясняет каждый шаг. Используйте его для проверки домашних заданий, решения задач или просто для того, чтобы быстро получить ответ — и вы убедитесь, что поиск простых чисел становится простым, когда всё разложено по полочкам.