Калькулятор простых чисел отвечает на один конкретный вопрос: делится ли введённое число на что-то, кроме единицы и себя самого. Введите число - и сразу увидите вердикт, а для составных чисел ещё и наименьший делитель. Ниже разберём, что такое простое число, на паре примеров с ручным счётом и почему единица в этот список не попадаёт.
Что такое простое число
Простое число - это натуральное число больше единицы, у которого только два делителя: единица и оно само. Ряд начинается с 2, 3, 5, 7, 11, 13, 17, 19, 23 и продолжается бесконечно - строгое доказательство этому дал ещё Евклид больше двух тысяч лет назад.
Число, у которого делителей больше двух, называют составным. 12, например, делится на 2, 3, 4 и 6, помимо единицы и себя самого - явно составное. Граница между двумя категориями и есть суть проверки: если находится хотя бы один делитель, кроме 1 и n, число составное.
Почему 1 не считается простым числом
У единицы всего один делитель - она сама. Определение простого числа требует ровно два делителя, так что единица под него не подходит и в число простых не входит. Это не произвольная договорённость: если бы единицу засчитывали как простое число, разложение любого числа на простые множители переставало бы быть единственным - к любому разложению можно было бы бесконечно дописывать единицы. Основная теорема арифметики требует, чтобы у каждого числа было ровно одно разложение на простые множители, и исключение единицы из списка простых это гарантирует.
Как проверить число на простоту: метод пробного деления
Самый прямой способ - пробное деление. Берём число n и по очереди делим его на 2, 3, 4 и так далее, проверяя остаток. Хитрость в том, что перебирать делители дальше квадратного корня из n бессмысленно: если у n есть делитель больше корня, у него обязательно найдётся парный делитель меньше корня, и он уже был бы найден раньше. Поэтому для проверки числа 200 достаточно дойти до 14, а не до 199.
Пример 1: проверяем число 97
Квадратный корень из 97 приблизительно равен 9,85, значит перебирать делители нужно только до 9. Число нечётное, на 2 не делится. Проверяем оставшиеся: 97 ÷ 3 = 32,33, 97 ÷ 5 = 19,4, 97 ÷ 7 = 13,857 - ни одно деление не дало целого числа. Делителей, кроме 1 и 97, не нашлось, значит 97 простое число.
Следующее простое после 97 находится перебором: 98 чётное, делится на 2. 99 равно 9 × 11, составное. 100 чётное. 101 - корень из него около 10,05, проверяем 3, 5, 7: не делится ни на одно, значит 101 простое. Именно его калькулятор и покажет как следующее простое число для 97.
Пример 2: ловушка с числом 91
91 выглядит простым - оно нечётное, не заканчивается на 0 или 5, сумма цифр 10 не делится на 3. Проверка по всем трём быстрым признакам ничего не находит, и на этом многие останавливаются, делая неверный вывод. Но перебор не закончен: следующий делитель для проверки - 7. 91 ÷ 7 = 13, ровно, без остатка. Значит 91 составное, а его наименьший делитель - 7 (91 = 7 × 13).
Этот случай - классическая ловушка при проверке на простоту вручную. Числа вроде 91, 119 или 133 не делятся на маленькие “очевидные” делители 2, 3 и 5, из-за чего их часто принимают за простые, хотя они раскладываются на два двузначных множителя. Отсюда и польза автоматической проверки: калькулятор не остановится раньше времени и доведёт перебор делителей до конца.
Зачем простые числа нужны на практике
Кроме чистой теории чисел, у простых чисел есть вполне прикладное применение - криптография. Алгоритмы вроде RSA строятся на том, что перемножить два больших простых числа - дело нескольких миллисекунд, а вот по готовому произведению восстановить исходные множители - задача, на которую даже современным компьютерам нужны годы или века при достаточно большой длине чисел. Эта асимметрия между лёгким умножением и тяжёлым разложением на множители лежит в основе шифрования банковских карт, защищённых соединений и цифровых подписей.
Простые числа также используются в хеш-функциях, генераторах псевдослучайных чисел и алгоритмах сжатия - там их свойства помогают равномерно распределять данные и избегать повторяющихся закономерностей.
Как пользоваться калькулятором
Введите любое целое число от 2 - калькулятор сразу покажет, простое оно или составное. Для составных дополнительно выводится наименьший делитель, а для любого числа - ближайшее следующее простое. Метод внутри тот же самый пробное деление до квадратного корня, только выполняется он мгновенно, даже для чисел с десятком-другим цифр, где ручной перебор занял бы часы.