Для вычисления n-го простого числа я знаю два основных варианта.
Простой способ
То есть считать все простые числа, начиная с 2, по мере их нахождения до достижения желаемого n th .
Это может быть сделано с различными уровнями сложности и эффективности, и есть два концептуально различных способа сделать это. Первый
Проверка простоты всех чисел в последовательности
Это будет выполнено с помощью функции драйвера, такой как
public static int nthPrime(int n) {
int candidate, count;
for(candidate = 2, count = 0; count < n; ++candidate) {
if (isPrime(candidate)) {
++count;
}
}
// The candidate has been incremented once after the count reached n
return candidate-1;
}
и интересная часть, которая определяет эффективность, - это функция isPrime.
Очевидный способ проверки простоты, учитывая определение простого числа как числа, большего 1, которое делится только на 1 и само по себе, которое мы изучили в школе¹, это
Пробный отдел
Прямой перевод определения в код:
private static boolean isPrime(int n) {
for(int i = 2; i < n; ++i) {
if (n % i == 0) {
// We are naive, but not stupid, if
// the number has a divisor other
// than 1 or itself, we return immediately.
return false;
}
}
return true;
}
но, как вы скоро обнаружите, если попробуете, его простота сопровождается медлительностью.
С помощью этого теста на простоту вы можете найти 1000 th штрих, 7919, за несколько миллисекунд (около 20 на моем компьютере), но поиск 10000 th штрих, 104729, занимает секунды (~ 2,4 с), 100000 th простое, 1299709, несколько минут (около 5), миллионное простое, 15485863, займет около восьми с половиной часов, десятимиллионное простое, 179424673, недели , и так далее. Сложность во время выполнения хуже, чем квадратичная - Θ (n² * log n).
Итак, мы бы хотели немного ускорить тест на первичность. Шаг, который делают многие люди, это осознание того, что делитель n (кроме самого n) может быть не более n/2.
Если мы используем этот факт и позволяем циклу пробного деления работать только до n/2 вместо n-1, как изменится время выполнения алгоритма?
Для составных чисел нижний предел цикла ничего не меняет. Для простых чисел число пробных делений уменьшается вдвое, поэтому в целом время выполнения должно быть уменьшено в несколько раз меньше, чем 2. Если вы попробуете это, вы обнаружите, что время выполнения почти точно уменьшено вдвое, поэтому почти все время тратится на проверку простоты простых чисел , несмотря на то, что составных частей гораздо больше, чем простых чисел.
Теперь, это не сильно помогло, если мы хотим найти стомиллионное простое число, поэтому мы должны добиться большего. Пытаясь еще больше уменьшить предел цикла, давайте посмотрим, для каких чисел действительно нужна верхняя граница n/2. Если n/2 является делителем n, то n/2 является целым числом, другими словами, n делится на 2. Но тогда цикл не идет после 2, поэтому он никогда (кроме n = 4) достигает n/2. Очень хорошо, так каков следующий по величине возможный делитель n?
Почему, конечно же, n/3 Но n/3 может быть делителем n, только если оно является целым числом, другими словами, если n делится на 3. Тогда цикл завершится в 3 (или раньше, в 2) и никогда не достигнет n/3 (кроме n = 9). Следующий по величине возможный делитель ...
Подождите минутку! У нас есть 2 <-> n/2 и 3 <-> n/3. Делители n делятся попарно.
Если мы рассмотрим пару (d, n/d) соответствующих делителей n, то либо d = n/d, т.е. d = √n, либо один из них, скажем d, будет меньше другого. Но тогда d*d < d*(n/d) = n и d < √n. Каждая пара соответствующих делителей n содержит (как минимум) единицу, не превышающую √n.
Если n является составным, его наименьший нетривиальный делитель не превышает √n.
Таким образом, мы можем уменьшить ограничение цикла до √n, и это уменьшает сложность алгоритма во время выполнения. Теперь он должен быть Θ (n 1.5 * √ (log n)), но эмпирически он, кажется, масштабируется немного лучше - однако, недостаточно данных, чтобы сделать надежные выводы из эмпирических результатов.
Это находит миллионное простое число примерно за 16 секунд, десятимиллионное - чуть меньше девяти минут, и оно находит сто миллионное за четыре с половиной часа. Это все еще медленно, но далеко от десяти лет или около того потребовалось бы наивное испытание дел.
Поскольку существуют квадраты простых чисел и произведений двух близких простых чисел, например 323 = 17 * 19, мы не можем уменьшить ограничение для цикла пробного деления ниже √n. Поэтому, оставаясь с пробным делением, мы должны искать другие способы улучшить алгоритм.
Одна легко заметная вещь состоит в том, что никакое простое число, отличное от 2, не является четным, поэтому нам нужно проверять нечетные числа только после того, как мы позаботимся о 2. Однако это не имеет большого значения, поскольку четные числа являются самый дешевый, чтобы найти составной - и большая часть времени все еще потрачена на проверку простоты простых чисел. Однако если мы посмотрим на четные числа в качестве возможных делителей, то увидим, что если n делится на четное число, само n должно быть четным, поэтому (за исключением 2) оно будет распознано как составное до деления на любое четное число больше 2 Таким образом, все деления на четные числа больше 2, которые происходят в алгоритме, должны обязательно оставлять ненулевой остаток. Таким образом, мы можем опустить эти деления и проверить делимость только на 2 и нечетные числа от 3 до √n. Это сокращает вдвое (не совсем точно) количество делений, необходимое для определения числа как простого или составного, и, следовательно, время выполнения. Это хорошее начало, но мы можем сделать лучше?
Другим большим семейством чисел является число, кратное 3. Каждое третье деление, которое мы выполняем, кратно 3, но если n делится на одно из них, оно также делится на 3, и, следовательно, деление на 9, 15, 21, ..., которые мы выполняем в нашем алгоритме, всегда оставляют остаток от 0.
Итак, как мы можем пропустить эти разделы? Ну, числа, делимые ни на 2, ни на 3, являются точными числами вида 6*k ± 1. Начиная с 5 (поскольку нас интересуют только числа больше 1), они равны 5, 7, 11, 13, 17, 19, ..., шаг от одного до следующего чередуется между 2 и 4, что достаточно просто, поэтому мы можем использовать
private static boolean isPrime(int n) {
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int step = 4, m = (int)Math.sqrt(n) + 1;
for(int i = 5; i < m; step = 6-step, i += step) {
if (n % i == 0) {
return false;
}
}
return true;
}
Это дает нам еще одно ускорение с коэффициентом (почти) 1,5, поэтому нам потребуется около полутора часов до стомиллионного простого числа.
Если мы продолжим этот маршрут, следующим шагом будет удаление кратных 5. Числа, взаимно простые с 2, 3 и 5, являются числами вида
30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29
поэтому нам нужно будет только разделить на восемь из каждых тридцати чисел (плюс три наименьших простых числа). Шаги от одного к следующему, начиная с 7, циклически перебираются через 4, 2, 4, 2, 4, 6, 2, 6. Это достаточно легко реализовать и дает еще одно ускорение с коэффициентом 1,25 (минус немного для более сложный код). Если пойти дальше, то множители 7 будут исключены, оставив 48 из каждых 210 чисел разделить на, затем 11 (480/2310), 13 (5760/30030) и так далее. Каждое простое число p, множители которого исключены, дает ускорение (почти) p/(p-1), поэтому отдача уменьшается, в то время как стоимость (сложность кода, место для таблицы поиска для шагов) увеличивается с каждым простым числом.
В общем, можно было бы вскоре остановиться, исключив кратные, возможно, шесть или семь простых чисел (или даже меньше). Здесь, однако, мы можем выполнить до самого конца, когда кратные числа всех простых чисел были удалены, и в качестве делителей-кандидатов остались только простые числа. Поскольку мы находим все простые числа по порядку, каждое простое число определяется до того, как оно понадобится в качестве делителя-кандидата, и затем может быть сохранено для будущего использования. Это уменьшает алгоритмическую сложность до - если я не просчитался - O (n 1.5 / √ (log n)). За счет использования пространства для хранения простых чисел.
При пробном делении, которое так хорошо, как оно получается, вы должны попытаться разделить все простые числа на √n или первое деление n, чтобы определить первичность n. Это находит стомиллионное простое число примерно через полчаса здесь.
Так как насчет
Быстрые тесты на простоту
Простые числа обладают другими теоретико-числовыми свойствами, чем отсутствие нетривиальных делителей, которых у составных чисел обычно нет. Такие свойства, если их можно быстро проверить, могут служить основой для вероятностных или детерминированных тестов на простоту. Такое типичное свойство связано с именем Пьера де Ферма, который в начале 17 th века обнаружил, что
Если p - простое число, то p - это делитель (a p -a) для всех a.
Это - так называемая "маленькая теорема Ферма" - в эквивалентной формулировке
Пусть p простое число и a не делится на p. Затем p делит p-1 - 1.
основа большинства распространенных быстрых тестов на простоту (например, Миллера-Рабина) и вариантов или аналогов, которые встречаются еще больше (например, Лукас-Селфридж).
Итак, если мы хотим узнать, является ли не слишком маленькое нечетное число n простым числом (четные и малые числа эффективно обрабатываются пробным делением), мы можем выбрать любое число a (> 1), которое не является кратное n, например, 2, и проверьте, делит ли n n-1 - 1. Так как n-1 становится огромным, это делается наиболее эффективно проверяя,
a^(n-1) ≡ 1 (mod n), то есть модульным возведением в степень. Если это сравнение не имеет места, мы знаем, что n является составным. Однако, если оно выполнено, мы не можем сделать вывод, что n является простым, например, 2^340 ≡ 1 (mod 341), но 341 = 11 * 31 является составным. Составные числа n такие, что a^(n-1) ≡ 1 (mod n) называются псевдопримерами Ферма для основания a.
Но такие случаи редки. Для любой базы a > 1, хотя существует бесконечное количество псевдопримесов Ферма для базы a, они намного реже, чем фактические простые числа. Например, существует только 78 псевдоприемов Ферма с базисом 2 и 76 псевдоприкрестов Ферма с базой 3 ниже 100000, но 9592 простых. Поэтому, если выбрать произвольное нечетное n > 1 и произвольное основание a > 1 и найти a^(n-1) ≡ 1 (mod n), есть большая вероятность, что n на самом деле простое.
Однако мы находимся в несколько иной ситуации, нам дают n и мы можем выбрать только a. Итак, для нечетного композита n, сколько a, 1 < a < n-1 может удержать a^(n-1) ≡ 1 (mod n)?
К сожалению, существуют составные числа - числа Кармайкла - такие, что конгруэнция выполняется для каждого a взаимно простого с n. Это означает, что для идентификации числа Кармайкла как составного с тестом Ферма мы должны выбрать базу, кратную одному из простых делителей n - таких кратных может не быть много.
Но мы можем усилить тест Ферма, чтобы композиты были более надежно обнаружены. Если p нечетное простое число, напишите p-1 = 2*m. Тогда, если 0 < a < p,
a^(p-1) - 1 = (a^m + 1) * (a^m - 1)
и p делит ровно один из двух факторов (два фактора отличаются на 2, поэтому их наибольший общий делитель равен 1 или 2). Если m четное, мы можем разделить a^m - 1 таким же образом. Продолжая, если p-1 = 2^s * k с k нечетным, напишите
a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)
затем p делит ровно один из факторов. Это приводит к сильному тесту Ферма,
Пусть n > 2 будет нечетным числом. Напишите n-1 = 2^s * k с k нечетным. Дано любое a с 1 < a < n-1, если
a^k ≡ 1 (mod n) или a^((2^j)*k) ≡ -1 (mod n) для любого j с 0 <= j < s
, тогда n является сильным (Ферма) вероятным простым числом для базы a.Составное сильное основание a (Ферма), вероятное простое число, называется сильным (Ферма) псевдоприм для основания a.Сильные псевдопраймы Ферма еще реже, чем обычные псевдопраймы Ферма, ниже 1000000, 78498 простых чисел, 245 псевдопраймов Ферма с базисом 2 и только 46 сильных псевдопригодов Ферма с базисом 2.Что еще более важно, для любого нечетного композита n существует не более (n-9)/4 оснований 1 < a < n-1, для которых n является сильным псевдоприродом Ферма.
Так что если n является нечетным композитом,вероятность того, что n пройдет k сильные тесты Ферма со случайно выбранными основаниями от 1 до n-1 (исключительные границы), меньше чем 1/4^k.
Сильный тест Ферма принимает O (log n) шаговкаждый шаг включает в себя одно или два умножения чисел с O (log n) битами, поэтому сложность O ((log n) ^ 3) с наивным умножением [для огромных n могут быть полезны более сложные алгоритмы умножения].
Тест Миллера-Рабина - это сильный критерий Ферма в k-кратном порядке со случайно выбранными основаниями.Это вероятностный тест, но для достаточно малых границ известны короткие комбинации оснований, которые дают детерминированный результат.
Сильные тесты Ферма являются частью детерминистического теста APRCL.
Рекомендуетсяпредшествовать таким испытаниям с пробным делением первыми несколькими небольшими простыми числами, поскольку деления сравнительно дешевы, и это отсеивает большинство композитов.
Для задачи нахождения простого числа n th ,в диапазоне, где выполнимо тестирование всех чисел на простоту, существуют известные комбинации оснований, которые делают корректным множественный сильный тест Ферма, так что это даст более быстрый результат - O (n * (log n) 4 )- алгоритм.
Для n < 2^32 базисов 2, 7 и 61 достаточно для проверки простоты.Используя это, стомиллионное простое число находится примерно за шесть минут.
Уничтожение композитов простыми делителями, Сито Эратосфена
Вместо того, чтобы исследовать числа в последовательности и проверять, простое ли каждое из нихс нуля можно также рассматривать весь набор соответствующих чисел как одно целое и исключать кратные данного простого числа за один раз.Это называется ситом Эратосфена:
Чтобы найти простые числа, не превосходящие N
- , составьте список всех чисел от 2 до
N - для каждого
k от 2 до N: если k еще не вычеркнуто, оно является простым;вычеркните все кратные k как композиты
Простые числа - это числа в списке, которые не вычеркнуты.
Этот алгоритм принципиально отличается от пробного деления, хотяоба напрямую используют характеристику делимости простых чисел, в отличие от теста Ферма и аналогичных тестов, в которых используются другие свойства простых чисел.
При пробном делении каждое число n соединяется со всеми простыми числами, не превышающими меньшего из√n и наименьший простой делитель n.Поскольку большинство композитов имеют очень маленький простой делитель, обнаружение композитов здесь в среднем дешево.Но тестирование простых чисел обходится дорого, поскольку ниже простых чисел √n относительно много.Хотя составных элементов гораздо больше, чем простых чисел, стоимость тестирования простых чисел настолько высока, что полностью доминирует в общем времени выполнения и делает сравнительный медленный алгоритм пробным делением.Пробное деление для всех чисел, меньших N, выполняется за O (N 1.5 / (log N) ²) шагов.
В сите каждый композит n связан со всеми своими простыми делителями, но только с ними.Таким образом, в качестве простых чисел используются дешевые числа, они только когда-либо просматриваются один раз, в то время как композиты стоят дороже, они вычеркиваются несколько раз.Кто-то может поверить, что, поскольку сито содержит гораздо больше «дорогих» чисел, чем «дешевых», в целом это будет плохой алгоритм.Однако составное число не имеет много различных простых делителей - число различных простых делителей n ограничено log n, но обычно оно на намного меньше, среднее число различныхпростые делители чисел <= n равны log log n, поэтому даже «дорогие» числа в сите в среднем не дороже (или чуть больше), чем «дешевые» числа для пробного деления.
При просеивании до N для каждого простого p необходимо вычесть Θ(N/p) кратных, поэтому общее число вычетов составляет Θ(∑ (N/p)) = Θ(N * log (log N)).Это дает намного более быстрых алгоритмов для нахождения простых чисел до N, чем пробное деление или последовательное тестирование с более быстрыми тестами на примитивность.
Однако у сита есть недостаток:использует O(N) память.(Но с сегментированным ситом, которое может быть уменьшено до O(√N) без увеличения временной сложности.)
Для нахождения n th простого числа вместо простых чисел до N, также существует проблема, заключающаяся в том, что заранее неизвестно, как далеко должно достигнуть сито.
Последнее можно решить с помощью теоремы о простых числах.PNT говорит:
π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1),
, где π(x) - число простых чисел, не превышающее x (здесь и далее log должно быть натуральным логарифмом, для алгоритмических сложностей не важно, какое основаниевыбран для логарифмов).Из этого следует, что p(n) ~ n*log n, где p(n) является n th штрихом, и существуют хорошие верхние оценки для p(n), известные из более глубокого анализа, в частности
n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.
Так что можно использовать это как предел просеивания, он не превышает дальность цели.
Требуемое пространство O(N) может быть преодолено с помощью сегментированного сита.Затем можно записать простые числа ниже √N для O(√N / log N) потребления памяти и использовать сегменты увеличивающейся длины (O (√N), когда сито близко к N).
В алгоритме есть несколько простых улучшенийкак указано выше:
- начните вычеркивать кратные
p только в p², а не в 2*p - удалить четные числа из сита
- исключить кратные числа следующих небольших простых чисел из сита
Ни одно из них не уменьшает алгоритмическую сложность, но все они значительно уменьшают постоянные факторы (как при пробном делении, устранение кратныхp дает меньшее ускорение при большем p при увеличении сложности кода больше, чем при меньшем p).
Использование первых двух улучшений дает
// Entry k in the array represents the number 2*k+3, so we have to do
// a bit of arithmetic to get the indices right.
public static int nthPrime(int n) {
if (n < 2) return 2;
if (n == 2) return 3;
int limit, root, count = 1;
limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
root = (int)Math.sqrt(limit) + 1;
limit = (limit-1)/2;
root = root/2 - 1;
boolean[] sieve = new boolean[limit];
for(int i = 0; i < root; ++i) {
if (!sieve[i]) {
++count;
for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) {
sieve[j] = true;
}
}
}
int p;
for(p = root; count < n; ++p) {
if (!sieve[p]) {
++count;
}
}
return 2*p+1;
}
, который находит сотнюМиллионное простое число, 2038074743, примерно за 18 секунд.Это время может быть сокращено примерно до 15 секунд (здесь, YMMV), сохраняя упакованные флаги, один бит на флаг, вместо boolean с, поскольку уменьшенное использование памяти обеспечивает лучшую локальность кэша.
УпаковкаФлаги, устраняющие также кратные 3 и использующие битовое перемешивание для более быстрого и быстрого подсчета,
// Count number of set bits in an int
public static int popCount(int n) {
n -= (n >>> 1) & 0x55555555;
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
return (n * 0x01010101) >> 24;
}
// Speed up counting by counting the primes per
// array slot and not individually. This yields
// another factor of about 1.24 or so.
public static int nthPrime(int n) {
if (n < 2) return 2;
if (n == 2) return 3;
if (n == 3) return 5;
int limit, root, count = 2;
limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
root = (int)Math.sqrt(limit);
switch(limit%6) {
case 0:
limit = 2*(limit/6) - 1;
break;
case 5:
limit = 2*(limit/6) + 1;
break;
default:
limit = 2*(limit/6);
}
switch(root%6) {
case 0:
root = 2*(root/6) - 1;
break;
case 5:
root = 2*(root/6) + 1;
break;
default:
root = 2*(root/6);
}
int dim = (limit+31) >> 5;
int[] sieve = new int[dim];
for(int i = 0; i < root; ++i) {
if ((sieve[i >> 5] & (1 << (i&31))) == 0) {
int start, s1, s2;
if ((i & 1) == 1) {
start = i*(3*i+8)+4;
s1 = 4*i+5;
s2 = 2*i+3;
} else {
start = i*(3*i+10)+7;
s1 = 2*i+3;
s2 = 4*i+7;
}
for(int j = start; j < limit; j += s2) {
sieve[j >> 5] |= 1 << (j&31);
j += s1;
if (j >= limit) break;
sieve[j >> 5] |= 1 << (j&31);
}
}
}
int i;
for(i = 0; count < n; ++i) {
count += popCount(~sieve[i]);
}
--i;
int mask = ~sieve[i];
int p;
for(p = 31; count >= n; --p) {
count -= (mask >> p) & 1;
}
return 3*(p+(i<<5))+7+(p&1);
}
находит стомиллионное простое число примерно за 9 секунд, что не является невыносимо долгим.
Существуют и другие типы простых сит, представляющих особый интерес. Это сито Аткина, в котором используется тот факт, что определенные классы конгруэнции (рациональных) простых чисел являются составными в кольце алгебраических целых чисел некоторых квадратичных расширений ℚ. Здесь не место углубляться в математическую теорию, достаточно сказать, что сито Аткина имеет меньшую алгоритмическую сложность, чем сито эратосфена, и, следовательно, предпочтительнее для больших пределов (для небольших пределов не слишком оптимизированное сито Аткина имеет более высокое и, следовательно, может быть медленнее, чем сравнительно оптимизированное сито Эратосфена).
Библиотека Дж. Бернштейна primegen (написанная на C) хорошо оптимизирована для чисел ниже 2 32 и находит стомиллионное простое число (здесь) примерно за 1,1 секунды.
Быстрый путь
Если мы хотим найти только n th простое число, то нет никакой внутренней ценности в нахождении также всех меньших простых чисел. Если мы сможем пропустить большинство из них, мы сможем сэкономить много времени и работы. Учитывая хорошее приближение a(n) к n th простое p(n), если у нас есть быстрый способ вычислить число простых чисел π(a(n)), не превышающее a(n), мы можем затем просеять небольшой диапазон выше или ниже a(n) для определения нескольких пропущенных или избыточных простых чисел между a(n) и p(n).
Мы видели легко вычисляемое довольно хорошее приближение к p(n) выше, мы могли бы взять
a(n) = n*(log n + log (log n))
например.
Хороший метод для вычисления π(x) - это метод Мейсселя-Лемера , который вычисляет π(x) примерно за O(x^0.7) время (точная сложность зависит от реализации, уточнение по Lagarias, Miller , Odlyzko, Deléglise и Rivat позволяют вычислить π(x) за O (x 2/3 / log² x) времени.
Начиная с простого приближения a(n), мы вычисляем e(n) = π(a(n)) - n. По теореме о простых числах плотность простых чисел около a(n) составляет около 1/log a(n), поэтому мы ожидаем, что p(n) будет около b(n) = a(n) - log a(n)*e(n), и мы просеем диапазон, немного больший, чем log a(n)*e(n). Для большей уверенности в том, что p(n) находится в просеянном диапазоне, можно увеличить диапазон, скажем, в 2 раза, что почти наверняка будет достаточно большим. Если диапазон кажется слишком большим, можно выполнить итерацию с лучшим приближением b(n) вместо a(n), вычислить π(b(n)) и f(n) = π((b(n)) - n. Как правило, |f(n)| будет намного меньше, чем |e(n)|. Если f(n) приблизительно равно -e(n), c(n) = (a(n) + b(n)) / 2 будет лучшим приближением к p(n). Только в очень маловероятном случае, когда f(n) очень близко к e(n) (и не очень близко к 0), находя достаточно хорошее приближение к p(n), что заключительный этап просеивания может быть выполнен за время, сравнимое с вычислениями π(a(n)) становится проблемой.
Как правило, после одного или двух улучшений начального приближения диапазон просеивания достаточно мал для того, чтобы стадия просеивания имела сложность O (n ^ 0,75) или выше.
Этот метод находит стомиллионное простое число примерно за 40 миллисекунд, а 10 12 -ое простое число, 29996224275833, меньше чем за восемь секунд.
tl; dr: Найти простое число n th можно эффективно, но чем эффективнее вы хотите, тем больше математики.
У меня есть Java-код для большинства обсужденных алгоритмов, подготовленный здесь , на случай, если кто-то захочет поиграть с ними.
remark Помимо замечаний для чрезмерно заинтересованных душ: определение простых чисел, используемое в современной математике, отличается, применимо в гораздо более общих ситуациях. Если мы адаптируем определение школы для включения отрицательных чисел - так что число является простым, если оно не равно ни 1, ни -1, а делится только на 1, -1, само по себе и его отрицательно - это определяет (для целых чисел) то, что в настоящее время называется неприводимый элемент ℤ, однако для целых чисел определения простых и неприводимых элементов совпадают.