Проверка простых чисел

• Мгновенная проверка простых чисел: Введите любое целое число до 10³⁰ и мгновенно узнайте, простое ли оно. Проверка простых чисел использует перебор делителей для небольших чисел и детерминированный тест Миллера-Рабина для больших чисел, давая математически точный ответ за миллисекунды.
• Безопасная онлайн-проверка простых чисел: Проверка простых чисел работает полностью на стороне клиента, в вашем браузере. Введённые значения никогда не отправляются на сервер, не сохраняются и не отслеживаются - полная приватность для криптографического, академического и исследовательского использования.
• Проверка простых чисел - без установки: Используйте проверку простых чисел прямо в любом современном браузере без загрузок, приложений и плагинов. Загружайте известные простые и составные числа одним кликом, проверяйте следующие 5 простых и перемещайтесь между простыми - 100% бесплатно и навсегда.
• Пошаговое доказательство и ближайшие простые: Проверка простых чисел показывает полные шаги перебора делителей для небольших чисел - каждый проверенный делитель с его остатком, - чтобы вы могли проследить доказательство. Она также показывает предыдущее простое, следующее простое, промежуток между простыми и следующие 5 простых после вашего числа.

• Криптография и безопасность: Криптографам нужны большие простые числа для генерации ключей RSA, обмена ключами Диффи-Хеллмана и криптографии на эллиптических кривых. Используйте проверку простых чисел, чтобы убедиться, что кандидаты в простые действительно просты, прежде чем применять их в криптографических протоколах.
• Математическое образование: Студенты, изучающие теорию чисел, используют проверку простых чисел для изучения распределения простых, проверки ответов домашних заданий и понимания алгоритма перебора делителей. Пошаговое доказательство делает её идеальным учебным инструментом для проверки простоты.
• Программирование и разработка алгоритмов: Разработчики, реализующие решёта простых, хеш-функции и алгоритмы теории чисел, используют проверку простых чисел для валидации своих реализаций. Мгновенно проверяйте крайние случаи, такие как 1, 2, большие простые числа Мерсенна и числа Кармайкла.
• Спортивное программирование: Спортивные программисты проверяют простые числа при решении конкурсных задач. Проверка простых чисел обрабатывает числа до 10³⁰ - намного больше, чем требуется в большинстве конкурсных задач, - и показывает ближайшие простые для задач о промежутках между простыми.
• Исследования в теории чисел: Математики, изучающие промежутки между простыми, простые-близнецы и распределения простых, используют проверку простых чисел для быстрой проверки простоты и поиска соседних простых. Функция следующих 5 простых облегчает изучение последовательностей простых.
• Занимательная математика и головоломки: Любители математики, проверяющие, являются ли интересные числа (например, 1729, число Харди-Рамануджана, или 561, первое число Кармайкла) простыми, используют проверку простых чисел для мгновенной проверки с понятным объяснением.

Простое число - это натуральное число больше 1, у которого нет положительных делителей, кроме 1 и самого себя. Первые простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Число 1 по определению не является простым. Число 2 - единственное чётное простое: все остальные чётные числа делятся на 2 и потому составные. Составное число - это любое целое число больше 1, которое не является простым: у него есть хотя бы один делитель, отличный от 1 и самого себя. Наша проверка простых чисел определяет, является ли любое целое число простым или составным, и показывает математическое доказательство, используя перебор делителей для небольших чисел и алгоритм Миллера-Рабина для больших чисел.

1. Введите ваше число: Введите любое целое число в проверку простых чисел. Поддерживаются числа до 10³⁰. Запятые и подчёркивания игнорируются, поэтому можно ввести 2 147 483 647 или 2_147_483_647. Нажмите любую кнопку пресета, чтобы мгновенно загрузить известное простое или составное число.
2. Тест на простоту: Нажмите «Проверить простоту», и проверка простых чисел автоматически выберет лучший алгоритм. Для чисел до 10¹⁵ используется перебор делителей - проверка делителей вида 6k±1 до √n - и показывается каждый шаг. Для больших чисел используется детерминированный тест Миллера-Рабина с 12 свидетелями, доказанный корректным для всех n < 3,3 × 10²⁴.
3. Просмотрите результаты: Проверка простых чисел отображает вердикт (ПРОСТОЕ или НЕ ПРОСТОЕ), наименьший делитель, если число составное, предыдущее и следующее простые с их промежутками, следующие 5 простых после вашего числа и полное пошаговое доказательство - всё обрабатывается локально в вашем браузере.

• Перебор делителей: Проверяет, делится ли n на какое-либо целое число от 2 до √n. Нужно проверять только делители вида 6k±1 (после отдельной обработки 2 и 3), что уменьшает объём работы в 3 раза. Точно и показывает каждый шаг, но медленно для очень больших чисел.
• Тест простоты Миллера-Рабина: Вероятностный тест, который при тщательно подобранных свидетелях становится детерминированным. С 12 свидетелями, используемыми нашей проверкой простых чисел (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37), тест детерминирован для всех n < 3 317 044 064 679 887 385 961 981.
• Числа Кармайкла: Числа вроде 561 = 3 × 11 × 17 проходят некоторые тесты на простоту, но являются составными. Тест Миллера-Рабина с несколькими свидетелями корректно определяет все числа Кармайкла как составные.
• Простые числа Мерсенна: Простые вида 2ⁿ − 1, например 2³¹ − 1 = 2 147 483 647. Они входят в число крупнейших известных простых чисел. Проверка простых чисел корректно определяет их с помощью Миллера-Рабина.

Промежуток между простыми - это разность между двумя последовательными простыми числами. Промежуток после 2 равен 1 (до 3), после 3 равен 2 (до 5), и промежутки в целом растут по мере увеличения чисел - хотя и неравномерно. Проверка простых чисел показывает промежуток как до предыдущего, так и до следующего простого. Крупнейшие известные промежутки между простыми изучаются в теории чисел в рамках понимания распределения простых. Согласно теореме о распределении простых чисел, средний промежуток вблизи n приблизительно равен ln(n).