Проверка числа на простоту

Проверка числа на простоту

Популярный AI Skill PRO

Введите расчет

Введите целое число больше 1.

Математическая формула

n=Число простое⇔n>1∧∄d∈[2,⌊n⌋]:nmodd=0n = \text{Число} \text{ простое} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0
Статистика использования

Реклама

Результаты

Результат для 91
составное
определение простоты числа
Число 91
Делители 1, 7, 13, 91
Предыдущее простое 89
Следующее простое 97

Сообщить об ошибке на этой странице

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

Простое число — это целое число больше 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
При пробном делении нужно проверять делители только от 2 до квадратного корня из \(n\).

Разбор на примере

Возьмём \(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? Да. Двойка — наименьшее простое число и единственное чётное среди простых. Предыдущего простого числа у неё нет.

Почему делители показываются только для составных чисел? У простого числа по определению есть лишь два делителя — единица и оно само, поэтому калькулятор просто сообщает об этом. У составных чисел делителей может быть много, и они выводятся в порядке возрастания.

Реклама

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

В таблице показано, как тест пробным делением обрабатывает семь чисел. Граница по квадратному корню равна \(\lfloor\sqrt{n}\rfloor\) — наибольший делитель, который нужно проверить. Если ни одно целое число от 2 до этой границы не делит \(n\), то \(n\) является простым. Предыдущее и следующее простые числа — это ближайшие простые числа, строго меньшие и строго большие \(n\).

Число n Статус Все делители Предыдущее простое Следующее простое Граница по квадратному корню \(\lfloor\sqrt{n}\rfloor\)
2 Простое 1, 2 нет 3 1 (проверять нечего; 2 — единственное чётное простое число)
9 Составное 1, 3, 9 7 11 3 (3 делит 9)
15 Составное 1, 3, 5, 15 13 17 3 (3 делит 15)
49 Составное 1, 7, 49 47 53 7 (7 делит 49)
91 Составное 1, 7, 13, 91 89 97 9 (7 делит 91)
97 Простое 1, 97 89 101 9 (2, 3, 5, 7, 9 не делят 97)
121 Составное 1, 11, 121 113 127 11 (11 делит 121)

Составные числа, похожие на простые: 49, 91 и 121 легко принять за простые, поскольку они нечётные и не делятся на 3 или 5.

  • \(49 = 7 \times 7\)
  • \(91 = 7 \times 13\)
  • \(121 = 11 \times 11\)

У каждого из них есть делитель, не превосходящий границу по квадратному корню, поэтому проверка только 2, 3 и 5 ошибочно сочла бы их простыми. Напротив, у 97 нет делителей до 9, поэтому оно простое.

Соглашения и граничные случаи

Каждый случай ниже был прогнан через этот калькулятор; в столбце результата — то, что он действительно возвращает.

СлучайВводРезультат
Простое ли 1?1ни простое, ни составное
Простое ли 2?2простое
Простое ли 0?0недопустимо

Проверено 2026-11-08

Ключевые термины и определения

Простое число
Натуральное число, большее 1, единственными положительными делителями которого являются 1 и само число (например, 2, 3, 5, 7, 97).
Составное число
Натуральное число, большее 1, имеющее хотя бы один делитель, отличный от 1 и от самого себя (например, 9, 49, 91). Числа 0 и 1 не являются ни простыми, ни составными.
Множитель / делитель
Целое число \(d\), которое делит \(n\) без остатка. Для 15 делители — 1, 3, 5, 15.
Остаток от деления (mod)
Остаток от деления. \(n \bmod d = 0\) означает, что \(d\) делит \(n\) точно. Например, \(91 \bmod 7 = 0\), а \(97 \bmod 7 = 6\).
Граница по квадратному корню
Если \(n = a \times b\) при \(a \le b\), то \(a \le \sqrt{n}\). Значит, у любого составного числа есть делитель между 2 и \(\lfloor\sqrt{n}\rfloor\), и проверять дальше не нужно.
Пробное деление
Тест на простоту, при котором \(n\) делится на кандидатов в делители от 2 до \(\lfloor\sqrt{n}\rfloor\). Если какое-либо деление даёт остаток 0, \(n\) составное; в противном случае оно простое. Метод прост и надёжен, а для умеренно больших чисел работает быстро.
Вид 6k±1
Каждое простое число, большее 3, можно записать как \(6k-1\) или \(6k+1\) при некотором целом \(k\), поскольку остальные остатки по модулю 6 делятся на 2 или 3. Это позволяет тесту пропустить около двух третей кандидатов в делители. Обратное неверно: 25, 35, 49 и 91 имеют такой вид, но являются составными.
Близнецы-простые числа
Два простых числа, отличающиеся на 2, например (3, 5), (11, 13), (17, 19) и (41, 43). Существует ли бесконечно много пар близнецов-простых чисел, — открытый вопрос математики.
Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика