Формулы, связанные с простыми числами, существуют, но нет простой школьной записи, которая без скрытых условий мгновенно выдаёт n-е простое для любого n. Это важное уточнение: математик может построить выражение, принимающее простые значения при специальных параметрах, или даже формально кодирующее всю последовательность, но такая формула часто не помогает вычислять простые быстрее обычных алгоритмов.
На практике простые числа ищут и проверяют процедурами: решетом для диапазона, вероятностными и детерминированными тестами для больших кандидатов, специальными алгоритмами для чисел определённой формы. Красота темы как раз в разнице между описанием распределения и эффективным вычислением конкретного следующего числа.
Простые числа определяются делителями, а не положением в таблице
Простое натуральное число больше единицы имеет ровно два положительных делителя — 1 и само себя. Последовательность начинается 2, 3, 5, 7, 11, 13. Уже первые десятки показывают нерегулярность промежутков: иногда простые идут через два, иногда возникает длинный составной участок.
Это не означает полного хаоса. Теорема о распределении простых говорит, что около большого x плотность простых порядка 1/ln x, а число простых до x примерно равно x/ln x. Мы хорошо понимаем статистический масштаб, но точное положение отдельного следующего простого остаётся дискретной задачей.
Красивые полиномы работают долго, но не бесконечно
Известный пример n²+n+41 даёт простое число для целых n от 0 до 39. Затем при n=40 получается 41² — составное число. Подобные конструкции впечатляют сериями, но фиксированный ненулевой полином с целыми коэффициентами не может выдавать простые для всех целых аргументов.
Причина проста: если при некотором аргументе значение равно p, то подходящие сдвиги аргумента могут сделать значение кратным p. Поэтому «найти полином, который всегда даёт простое» в наивном смысле нельзя.
Формула Миллса существует, но прячет сложность в константе
Теорема Миллса утверждает существование константы A, такой что целая часть A^(3^n) является простой для всех положительных n. На первый взгляд это и есть мечта о формуле простых. Но точное значение константы строится с использованием информации о расположении самих простых и зависит от глубоких результатов о промежутках между ними.
То есть формула замечательна теоретически, но не является бесплатным генератором. Это общий урок: математическое «существует выражение» и вычислительное «мы получили эффективный алгоритм» — разные утверждения.
Решето и тесты простоты делают реальную работу
Если нужно найти все простые до некоторого N, решето Эратосфена последовательно вычёркивает кратные уже найденных простых. Современные варианты оптимизируют память и работу с большими диапазонами, но исходная идея остаётся узнаваемой спустя две тысячи лет.
Для огромного отдельного кандидата делить его на все числа до квадратного корня неэффективно. Используют тесты простоты. Miller–Rabin очень быстро даёт вероятностную проверку с контролируемо малой ошибкой; существуют и доказательные алгоритмы, включая ECPP и теоретически полиномиальный AKS. Для чисел Мерсенна есть особенно быстрый тест Люка—Лемера.
Простота и факторизация — не одна задача
Можно сравнительно быстро доказать, что число составное, не находя его множители, и можно доказать простоту, не перебирая все возможные делители. Факторизация большого составного числа может быть намного труднее. Эта асимметрия лежит в основе классических криптосистем вроде RSA, хотя современная криптография использует и другие математические задачи.
Поэтому вопрос «есть ли формула простых чисел?» имеет несколько ответов. Формальные генераторы есть, статистические законы есть, глубокие гипотезы о распределении есть. Но для вычислений математика выбирает алгоритм под задачу, а не ждёт одной магической формулы.
Отдельная большая тема — промежутки между простыми. Они могут быть сколь угодно большими: последовательность n!+2, n!+3, …, n!+n состоит из составных чисел. Одновременно существуют бесконечно многие пары простых на ограниченном расстоянии друг от друга согласно современным результатам о bounded gaps, хотя знаменитая гипотеза близнецов для разницы ровно 2 всё ещё не доказана.
Риманова гипотеза связывает распределение простых с нулями дзета-функции. Её доказательство не дало бы «простую формулу n-го простого», но резко уточнило бы ошибки в приближениях и множество связанных результатов. Это ещё один пример того, как вопрос школьного вида выводит на одну из центральных нерешённых задач математики.
