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

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

Популярный 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
Статистика использования

Реклама

Результаты

Результат для 2
простое
определение простоты числа
Число 2
Делители Его единственные делители — 1 и 2
Предыдущее простое Предыдущего простого числа нет
Следующее простое 3

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

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

Простое число — это целое число больше 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). Существует ли бесконечно много пар близнецов-простых чисел, — открытый вопрос математики.
Последнее обновление:

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

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