Что такое простое число?
Простое число — это целое число больше 1, у которого ровно два положительных делителя: единица и само число. У составного числа делителей больше двух. Число 1 стоит особняком: у него всего один делитель, поэтому его не относят ни к простым, ни к составным. Этот калькулятор определяет, простое или составное введённое вами число, выводит список его делителей и показывает ближайшее простое число до и после него.
Как пользоваться калькулятором
Введите в поле целое число больше 1 и нажмите кнопку. Инструмент определит, простое оно или составное, повторит само число, перечислит все его делители (для составных чисел), а также покажет наибольшее простое число меньше введённого и наименьшее простое число больше него.
Как это работает
Мы используем детерминированное пробное деление с оптимизацией \(6k\pm1\). Сначала отдельно отмечаем 2 и 3 как заведомо простые числа и отсеиваем чётные числа и кратные трём. Затем проверяем только кандидаты в делители вида \(6k-1\) и \(6k+1\) (5, 7, 11, 13, ...) вплоть до квадратного корня из \(n\). Если ни один из них не делит \(n\) нацело, число простое. Проверять достаточно лишь до квадратного корня: любой делитель больше корня обязательно образует пару с делителем меньше корня.
$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$
Разбор на примере
Возьмём \(n = 97\). Квадратный корень из него примерно равен 9,85. Число нечётное и не кратно трём. Проверяем 5 (\(97 \bmod 5 = 2\)) и 7 (\(97 \bmod 7 = 6\)). Следующий кандидат — 11, но \(11 \times 11 = 121 > 97\), поэтому останавливаемся. Ни одного делителя не нашлось, значит, 97 — простое число. Предыдущее простое число — 89, следующее — 101.
Частые вопросы
Является ли 1 простым числом? Нет. У единицы только один делитель, поэтому её не относят ни к простым, ни к составным числам.
Простое ли число 2? Да. Двойка — наименьшее простое число и единственное чётное среди простых. Предыдущего простого числа у неё нет.
Почему делители показываются только для составных чисел? У простого числа по определению есть лишь два делителя — единица и оно само, поэтому калькулятор просто сообщает об этом. У составных чисел делителей может быть много, и они выводятся в порядке возрастания.
