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

Мгновенно определяйте, является ли любое число простым. Для составных чисел отображается полное разложение на простые множители. Также генерируйте списки простых чисел в любом диапазоне, ищите следующее/предыдущее простое число и изучайте закономерности — полезно для учёбы по математике, основ криптографии и теории чисел.

Ограничения на ввод нет: числа в пределах безопасного целочисленного диапазона JavaScript идут по быстрому пути пробного деления, а всё, что больше, передаётся детерминированному тесту Миллера-Рабина на BigInt, поэтому простые числа криптографического масштаба проверяются точно. Дерево факторизации показывает каждый шаг (84 → 2 × 42 → 2 × 21 → 3 × 7); для очень больших составных чисел остаточный сомножитель выше 10^7 показывается, а не раскладывается дальше. Поиск по диапазону ограничен 10 миллионами записей, чтобы результаты оставались прокручиваемыми, и можно сразу найти N-е простое число для задач по программированию и упражнений по теории чисел.

Как использовать

1. Введите любое натуральное число, чтобы проверить, является ли оно простым — результат мгновенный даже для больших чисел.
2. Для составных чисел просматривайте полное дерево разложения на простые множители. Для простых — ближайшие простые числа выше и ниже.
3. Используйте поиск по диапазону для вывода всех простых чисел между двумя значениями или генерируйте первые N простых чисел.

Когда использовать

• Проверить ответ домашнего задания по теории чисел или дискретной математике.
• Выбрать простой модуль для хэш-функции или учебного криптографического примера.
• Сгенерировать первые N простых чисел для задачи Project Euler или олимпиадного программирования.

Результат

Введите 97, и это простое число. Введите 84, и оно не простое, множители: 2² × 3 × 7. Сгенерируйте все простые числа от 1 до 100, чтобы увидеть все 25 в этом диапазоне.

Частые вопросы

Сколько занимает проверка очень большого числа?

Заметно меньше 10 миллисекунд для типичных входов. Миллер-Рабин с детерминированным набором свидетелей делает порядка O(log³ n) модульных возведений, так что даже число из десятков цифр завершается за пару десятков умножений. Интерфейс отвечает мгновенно — что для 12-значного числа, что для простого числа криптографического масштаба.

Простое разложение всегда единственно?

Да. Основная теорема арифметики гарантирует, что у любого целого числа больше 1 ровно одно простое разложение с точностью до порядка множителей. Инструмент сортирует множители по возрастанию и группирует повторы степенями (84 = 2² × 3 × 7), как в учебнике.

Какое максимальное число можно проверить?

Фиксированного предела нет. Числа в пределах безопасного целочисленного диапазона JavaScript идут по более быстрому пути пробного деления, а более крупные входы обрабатывает тест Миллера-Рабина на BigInt. Этот тест доказуемо точен для каждого числа меньше 3,3 × 10^24 и остаётся исключительно надёжным вероятностным тестом простоты далеко за этим пределом, так что он свободно проверяет простые числа криптографического масштаба.

Почему 0 и 1 не считаются простыми?

Простое число определяется как положительное целое, имеющее ровно два различных делителя: 1 и само себя. У 1 только один делитель (само), поэтому оно не подходит; у 0 делителей бесконечно много. Их исключение делает единственность разложения справедливой без оговорок.

Как простые числа связаны с реальной криптографией?

RSA выбирает два простых числа примерно по 1024 бита, перемножает их и публикует произведение как часть открытого ключа. Сложность разложить это произведение обратно на два множителя и обеспечивает безопасность RSA. Тест простоты при этом остаётся быстрым.

Похожие инструменты