Калькулятор простых чисел

n — простое <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1 000 000) = 1 000 003

n

Целое число, которое проверяется, — от 2 до 1 000 000. Нижняя граница выбрана намеренно, а не унаследована: предыдущего простого для 1 не существует, поэтому страница, принимающая 1, имела бы строку, которую нельзя честно заполнить. Вопрос о том, простое ли 1, — это вопрос определения, и на него отвечают вопросы ниже, а не калькулятор

d(n)

Число положительных делителей: это первая строка результата и единственное доказательство, на котором держится вердикт. d(n) = 2 означает, что число делят ровно два числа, а это и есть определение простого. Значение берётся из общей рутины теории чисел, поэтому оно совпадает с тем, что показывают страница делителей и страница разложения на простые множители для того же ввода

d(n) = 2

Сама проверка, записанная уравнением. Это эквивалентность, а не приближение: число простое тогда и только тогда, когда у него ровно два делителя. Для 97 делители — 1 и 97, значит их два и значок показывает «простое». Для 100 это 1, 2, 4, 5, 10, 20, 25, 50 и 100, значит их девять и значок показывает «составное»

previousPrime(n)

Наибольшее простое число, не превосходящее n. Граница включительная, поэтому для простого n ответом будет само n. Для 100 ответ 97; для 25 — 23; для 97 — 97. Интервал замкнут потому, что иначе понадобилось бы правило на случай, когда n уже простое, а пустая строка в панели результата читается как сбой, а не как факт

nextPrime(n)

Наименьшее простое число, не меньшее n, с тем же включительным правилом снизу. Для 25 это 29, для 100 — 101, для 97 — 97. Этот ответ может выйти за диапазон ввода: nextPrime(1 000 000) равен 1 000 003, то есть простому числу больше любого, которое страница принимает, и оно показывается как ответ, а не считается выходом за границы

от 1e6 до 1e6 + 100

Окрестность верхней границы ввода и то, почему там нужна отдельная проверка. Простые рядом с миллионом — это 999 983 и 1 000 003, поэтому поиск от 1 000 000 должен в одну сторону заглянуть за миллион. Рутина, считающая делители, отказывается принимать аргументы больше миллиона и бросила бы исключение, поэтому поиск соседей использует собственную проверку без такого ограничения — и обе обязаны совпадать там, где перекрываются; именно это и проверяют строки с простыми числами в примерах

Выбор модуля — самая практичная причина хотеть простое число рядом с уже выбранным. Число ячеек хеш-таблицы обычно берут простым, потому что простой модуль разносит ключи, у которых есть общий множитель, вместо того чтобы сваливать их в одни и те же ячейки: таблица на 1000 ячеек отправит все кратные 25 в несколько общих позиций, а таблица на 997 — нет. Та же логика работает в криптографии, где ключи строят из простых чисел, больших и далёких друг от друга. Проверка на простоту заодно быстро закрывает вопросы делимости: если у числа нет простого делителя до его квадратного корня, то нет и никакого, и значок отвечает на это одним шагом — перебор делителей до корня для этого не нужен. Некоторые задачи и вовсе только про простоту — числа-близнецы, промежутки между соседними простыми и вопрос, является ли данное число произведением двух простых. Там, где речь в итоге заходит о самих множителях, число разбирает страница, где оно раскладывается на простые множители, и это естественный следующий шаг; там, где нужно узнать, какие числа делят ваше, их все перечисляет страница делителей; а там, где проверяемое число не простое и хочется понять, из чего оно состоит, число делителей на этой странице — первая подсказка, а не полный ответ.

1. Простое число: 97

   1. Проверяем делители 97: на 2 оно не делится, как и на 3, 5, 7 и 11
   2. Останавливаемся на квадратном корне: 10 × 10 = 100 уже больше 97, проверять больше нечего
   3. Делители только 1 и 97, значит их два, и число простое
   4. Предыдущее простое — само 97: оно уже простое, а поиск идёт включительно
   5. Следующее простое тоже 97, по той же причине

   Ввод по умолчанию и самый наглядный случай включительного правила. Оба соседа возвращаются как само число, и поначалу это выглядит так, будто строки ничего не сделали. Они сделали: наибольшее простое, не превосходящее 97, — это 97, и наименьшее простое, не меньшее 97, — тоже 97. Альтернатива со строгим неравенством оставила бы эти две строки без ответа ровно на тех вводах, где страница наиболее уверена, а пустая строка в панели результата читается как сбой. Здесь же встречаются обе независимые проверки страницы: число делителей говорит 2, поиск соседей подтверждает, что 97 простое, и код для этого используется разный.

2. Составное число: 100

   1. 100 чётное, значит делится на 2; оно оканчивается на 00, поэтому на 4, 5, 10, 20, 25 и 50 оно тоже делится
   2. Делители — 1, 2, 4, 5, 10, 20, 25, 50 и 100, всего девять
   3. Девять больше двух, поэтому значок показывает «составное», а не «простое»
   4. Наибольшее простое не больше 100 — это 97; наименьшее не меньше — 101
   5. Оба соседа на шаг в сторону от числа: так и выглядит составное число посреди промежутка

   Случай, в котором соседи делают настоящую работу. Когда число составное, две эти строки и есть полезный вывод: они отвечают на следующий вопрос читателя — если не это число, то какое? Девяносто семь и сто один — ближайшие простые, и 100 стоит между ними. На число делителей тоже стоит взглянуть: оно нечётное, а так бывает ровно тогда, когда число является полным квадратом, и 100 — это 10 в квадрате. То есть один взгляд на счётчик уже говорит кое-что о форме числа, ещё до всякого разложения.

3. Число сразу после простого: 25

   1. Делители 25 — 1, 5 и 25, их три, потому что 5 образует пару само с собой
   2. Три больше двух, значит 25 составное
   3. Идём вниз от 25: 24, 23 — 23 простое, поэтому оно предыдущее простое
   4. Идём вверх от 25: 26, 27, 28, 29 — 29 простое, поэтому оно следующее простое
   5. Разрыв здесь шесть: 23 и 29 стоят вокруг 25

   Полный квадрат — отсюда и нечётное число делителей; и случай, где соседи стоят на заметно разном расстоянии: два снизу и четыре сверху. Тройка в счётчике показывает заодно, почему порог равен именно двум, а не числу простых множителей: у 25 простой множитель всего один, 5, но простым оно не является, и число делителей ловит это, даже не заглядывая в разложение.

Ввод должен быть целым числом от 2 до 1 000 000. Ноль и единица не принимаются, причём единица отклоняется по другой причине, чем ноль: это вопрос определения, а не число вне диапазона, и предыдущего простого для 1 не существует. Отрицательные числа не принимаются — простота является свойством целых чисел больше 1, и хотя в некоторых разделах математики существует соглашение об отрицательных простых, эта страница его не перенимает. Дробные числа не принимаются и не округляются. Потолок в миллион относится только к вводу: две строки с соседями могут законно показать простое число за его пределами, и следующее простое после миллиона — это 1 000 003, которое показывается, а не отклоняется. В основе вердикта лежит перебор делителей до квадратного корня; при таком размере он мгновенный, а на числе из двадцати цифр безнадёжен, и эта граница — свойство самой задачи, а не данной реализации. Страница сообщает три числа и значок: она не выводит список делителей, не раскладывает составное число на множители и проверяет по одному числу за раз, а не диапазон. Таблицы ниже — это фиксированные строки, а не ответ на ваш ввод. И наконец, простое число показывается как своё же предыдущее и следующее простое: это намеренный выбор замкнутого интервала, а не две строки, которые ничего не нашли.

Является ли 1 простым числом?

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

Почему предыдущее и следующее простое оба оказываются самим числом?

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

Почему следующее простое может быть больше миллиона, если ввод — нет?

Потому что граница ограничивает то, о чём можно спросить, а не то, каким может быть ответ. Следующее простое после 1 000 000 — это 1 000 003, и отказ его печатать означал бы отказ отвечать на вполне корректно поставленный вопрос о вводе, который страница приняла. Поэтому поиск соседей работает на собственной проверке, без верхней границы, а число делителей по-прежнему берётся из общей рутины, покрывающей только диапазон. Из этого следует, что о простоте числа судят два куска логики — один ограниченный, другой нет, — и там, где они перекрываются, они обязаны совпадать; именно это и проверяет пример с 97: счётчик говорит 2, а поиск соседей говорит, что 97 простое.

Где простые числа вообще применяются?

В основном для выбора размеров. Хеш-таблицам обычно дают простое число ячеек, потому что простой модуль разносит ключи, у которых есть общий множитель: таблица на 1000 ячеек отправит все кратные 25 в несколько одних и тех же позиций, а таблица на 997 — нет. То же соображение работает всюду, где счётчик движется по кругу: длина цикла, являющаяся простым числом, не вступает в резонанс с регулярными закономерностями в данных. Второе большое применение — криптография: ключи строят из простых чисел, которые одновременно очень велики и далеко отстоят друг от друга, а стойкость опирается на то, насколько трудно разложить их произведение обратно на эти два простых. Мелких применений масса: проверить утверждение о делимости, выяснить, является ли число произведением двух простых, и классические задачи про числа-близнецы и промежутки между соседними простыми.

Как страница принимает решение и насколько оно надёжно?

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

Почему показано число делителей, а не только вердикт?

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

• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)