Иллюстрированный самоучитель по Mathematica 5

Тест на простоту. Функция PrimeQ.

Чтобы сказать, является ли простым заданное число из 15 или 20 цифр, не хватит всей жизни, даже если использовать все, что уже известно.

Мерсенн, XVII в.

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

К. Ф. Гаусс
"Disquisitiones Arithmeticae" ("Арифметические исследования ")

Функция PrimeQ

Здесь я хотел бы сказать несколько слов о том, как трудно решить, является ли заданное число простым.

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

Вальтер Боро.
Дружественные числа.
Открытая лекция, прочитанная при вступлении в должность в Боннском университете

В предыдущей главе, разлагая числа на простые множители, нам уже приходилось проверять числа на простоту. Как вы помните, для этого служит функция PrimeQ, название которой заканчивается прописной буквой Q (question – вопрос), что означает, что она в качестве значения выдает True или False. Числа, ассоциированные с 1 (например, 1 и -1), она к простым не относит.

Кроме того, как и следует ожидать, она применима и к целым отрицательным числам, причем PrimeQ[-n] = PrimeQ[n]. Более того, она применима к целым гауссовым числам, и если ее аргумент – число с ненулевой мнимой частью, она осуществляет проверку на простоту именно в области гауссовых чисел. Однако если вы хотите в кольце гауссовых чисел проверить на простоту число с нулевой мнимой частью, придется указать опцию GaussianIntegers › True.