Проверка числа на простоту
Проверьте целое число до миллиарда на простоту и найдите наименьший делитель составного числа.
Результат проверки
97 — простое число
- Проверено до
- √97 ≈ 9,849
Что считает калькулятор
Если число составное, хотя бы один его делитель не превышает квадратного корня, поэтому дальше проверять не требуется.
Калькулятор показывает не только ответ, но и подстановку в формулу, чтобы вычисление можно было проверить вручную.
Формула
n простое ⇔ не существует d: 2 ≤ d ≤ √n и n mod d = 0
- n
- проверяемое положительное целое число
- d
- возможный делитель
- mod
- остаток от деления
- Число 1 не относится ни к простым, ни к составным.
- Проверка выполняется точным перебором допустимых делителей.
Примеры
Расчёт при значениях по умолчанию: n = 97
- Исходные данные: n = 97.
- Подстановка и вычисление: Делители от 2 до √97 не найдены..
- Проверено до: √97 ≈ 9,849.
Результат проверки: 97 — простое число
Частые вопросы
›Почему достаточно проверять до √n?
Если оба множителя были бы больше √n, их произведение оказалось бы больше n.
Источники
- Элементарная теория чисел — делимость, простые числа и сравнения
Методика проверена