Что такое простое число?
Простое число — это целое число больше 1, у которого ровно два различных положительных делителя: единица и само число. Классические примеры — 2, 3, 5, 7, 11 и 13. Числа больше 1, которые не являются простыми, называют составными: их можно представить как произведение меньших целых чисел. Этот калькулятор мгновенно подскажет, простое ли введённое вами число, а если нет — покажет наименьший делитель, на который оно делится.
Как пользоваться калькулятором
Введите любое целое число (от 0 и больше) в поле ввода и нажмите кнопку. В итоговом блоке появится ДА, если число простое, или НЕТ, если оно составное. Для составного числа в таблице отобразится наименьший делитель, больший 1, — с него удобно начать полное разложение на множители.
Разбираем формулу
Чтобы быстро проверить число на простоту, достаточно перебрать делители только до квадратного корня из \(n\). Если у \(n\) есть множитель больше корня из него, то обязательно найдётся и парный множитель меньше этого корня — поэтому проверки до корня вполне хватает. Формально: \(n\) простое, когда
$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$то есть \(n \bmod i \neq 0\) для каждого целого \(i\) от 2 до \(\lfloor\sqrt{n}\rfloor\). Это в разы сокращает объём вычислений по сравнению с перебором всех чисел до \(n\).
Разбор примера
Возьмём \(n = 97\). Квадратный корень из него — примерно \(9{,}85\), поэтому проверяем делители 2, 3, 5, 7 и 9. Ни один из них не делит 97 нацело (97 нечётное и не делится ни на 3, ни на 5, ни на 7), значит, 97 — простое. Теперь возьмём \(n = 91\). Перебираем 2, 3, 5, затем 7 — и обнаруживаем, что
$$91 \div 7 = 13$$без остатка. Следовательно, 91 — составное, а его наименьший делитель равен 7.
Частые вопросы
Является ли 1 простым числом? Нет. По определению простое число должно быть больше 1, поэтому единица не относится ни к простым, ни к составным числам.
Простое ли число 2? Да. Двойка — единственное чётное простое число; все остальные чётные числа делятся на 2.
Почему проверка идёт только до квадратного корня? Делители идут парами, произведение которых равно \(n\). Если бы оба делителя в паре были больше \(\sqrt{n}\), их произведение превысило бы \(n\), что невозможно. Значит, хотя бы один делитель из каждой пары не превышает \(\sqrt{n}\).
