Проверка простых чисел (с разложением на множители)

Введите неотрицательное целое число до 10^18. Калькулятор проверяет простоту методом пробного деления (детерминированно до ~10^15 за разумное время) и даёт разложение на простые множители для составных чисел.

Число

✓

является простым

Предыдущее простое число: 89
Следующее простое число: 101

Как это работает

Что такое простое число

Простое число — это натуральное число, большее 1, которое не имеет положительных делителей, кроме 1 и самого себя. Первые простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Это «атомы» целочисленной арифметики — каждое целое число ≥ 2 можно однозначно записать в виде произведения простых (основная теорема арифметики).

1 не является простым по определению. 0 и отрицательные числа тоже не простые. 2 — единственное чётное простое число: все остальные чётные числа делятся на 2, а значит, составные.

Как работает проверка

Используется метод пробного деления: проверяется делимость на 2, затем 3, 5, 7, 11, … вплоть до √n. Если ни одно не делит нацело, n — простое. Применяется оптимизация 6k±1: проверяются только кандидаты вида 6k+1 или 6k−1 (поскольку все простые числа > 3 имеют такую форму), что сокращает число проверок на 2/3.

Пробное деление быстро работает для n до ~10^15 (доли секунды). При бо́льших числах нужны продвинутые тесты — вероятностный Миллера–Рабина или детерминированный AKS. Ограничение 10^18 введено, чтобы браузер не зависал на экстремальных входных данных.

Почему простые числа важны

Криптография: шифрование RSA перемножает два простых числа длиной ~300 цифр, получая число, трудно поддающееся разложению. Безопасность основана на сложности факторизации больших чисел — задача, изучаемая тысячи лет.

Математическое образование: разложение на простые множители — основа многого. Понятия НОД, НОК, модульная арифметика, дроби и теория чисел — всё строится на структуре простых множителей.

Информатика: размеры хеш-таблиц, генераторы случайных чисел и многие алгоритмы используют простые числа из-за их особых свойств делимости.

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

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

Нет. 1 — «единица», не простое. У простых чисел ровно два различных положительных делителя (1 и само число); у 1 — только один.

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

Нет. Простые числа — целые числа, большие 1.

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

Да — 2 единственное чётное простое число. Все остальные чётные числа имеют делитель 2 помимо 1 и самого числа.

›Как находится следующее простое число?

Последовательным перебором от n+1 с проверкой простоты на каждом шаге. Между любыми двумя соседними простыми числами всегда есть простое в диапазоне n × ln(n), поэтому поиск быстро завершается даже для больших чисел.

›Почему максимум — 10^18?

JavaScript BigInt может работать с бо́льшими числами, но пробное деление становится медленным. 10^18 — безопасный предел для проверки за долю секунды. Для больших чисел используйте специализированные инструменты типа SymPy или Mathematica.

›Можно ли проверить 1000-значное число?

С этим инструментом — нет: пробное деление слишком медленно для таких масштабов. В криптографии используются вероятностные тесты Миллера–Рабина для простых чисел с 1024 битами (~300 знаков).

›Что такое простое число Мерсенна?

Простое число вида 2^p − 1. По состоянию на 2025 год известны только 51 такое число. Наибольшее известное простое число (M82589933) является числом Мерсенна с ~25 миллионами цифр.

›Данные отправляются на сервер?

Нет. Вычисления выполняются локально в браузере.