§ 4.4. Праймориальная формула

Напомним, что факториалом натурального числа называется произведение всех положительных целых чисел, не превосходящих Аналогично мы определяем праймориал простого как произведение всех простых чисел, меньших или равных Например, Заметим,

что если следующее после простое число, то

Мы хотим рассмотреть числа вида Чтобы понять, зачем, посмотрите на таблицу:

(см. скан)

Все числа в правом столбце таблицы — простые! Может ли это быть просто совпадением? Если этот вопрос вселяет в вал надежду на то, что все числа вида простые, вам бы следовало попытаться заполнить следующую строку таблицы. На самом деле,

является составным числом.

Однако, хотя не всегда простое, мы можем показать, что оно не имеет делителей, меньших или равных Воспользуемся методом «от противного». Предположим, что простой делитель числа Поскольку — произведение всех простых чисел вплоть до должно также делить Следовательно, делит разность

Значит, что противоречит его простоте. В итоге мы получаем: наименьший делитель числа должен быть больше

Это наблюдение может навести на мысль о следующем алгоритме получения больших простых чисел. Пусть мы знаем

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

Описанный подход плох по нескольким причинам. Наиболее очевидная из них — необходимость разложения на простые множители числа Даже для сравнительно небольших значений праймориал огромен и разложение его на множители весьма проблематично.

С другой стороны, если повезет, число может оказаться простым. А как мы увидим позже, существуют вполне приемлемые способы проверки простоты больших чисел, которые не используют разложения на множители. Простое число, представимое в такой форме, называется праймориалъ-но простым. Конечно, остается наивный подход к проверке простоты, заключающийся в систематических попытках подобрать подходящий делитель числа. Как мы видели в §3.3, этот алгоритм весьма неэффективен. Специальный алгоритм тестирования простоты чисел вида будет изучаться в главе 11. Несмотря на то, что он очень удобен, пока найдено только 16 праймориально простых, наибольшее из которых соответствует и насчитывает 10387 знаков.

Итак, праймориальная формула не дает очень уж удобного пути к отысканию больших простых чисел; к счастью, на ней свет клином не сошелся.