Проверка простых чисел

Это число простое?

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

Что делает число простым?

Определение простое: целое положительное число является простым, если его единственные положительные делители равны 1 и самому себе. Число 7 является простым, потому что его можно разделить поровну только на 1 и 7. Число 8 не является простым — оно также делится на 2 и 4. Число 1 — это особый случай: согласно современным математическим соглашениям оно не считается простым, потому что его включение нарушило бы уникальность факторизации простых чисел.

Первые несколько простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Обратите внимание, что 2 — единственное четное простое число, поскольку все остальные четные числа делятся на 2.

Тестирование на примитивность в больших масштабах

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

Простая факторизация

Основная теорема арифметики утверждает, что каждое целое число больше 1 можно выразить как произведение простых чисел ровно одним способом, с точностью до порядка множителей. Это называется простой факторизацией. Например: 12 = 2 × 2 × 3, записанное как 2² × 3. Число 360 = 2³ × 3² × 5. Найти разложение числа на простые множители означает разбить его на простые компоненты, что раскрывает его математическую структуру.

Почему простые числа имеют значение

Простые числа являются строительными блоками всех целых чисел: каждое составное (непростое) число можно получить путем умножения простых чисел. Это делает их центральными в теории чисел — разделе математики, изучающем свойства целых чисел.

В современных вычислениях сложность разложения больших чисел на их основные компоненты лежит в основе шифрования RSA, которое защищает большую часть зашифрованных сообщений в Интернете. Два больших простых числа перемножаются для создания открытого ключа. Разложить это произведение обратно на простые числа — не зная их заранее — вычислительно невозможно для достаточно больших чисел.

Как работает проверка

Инструмент использует пробное деление: он проверяет, делится ли число на любое целое число от 2 до квадратного корня из числа. Если такой делитель существует, число является составным, и инструмент записывает его множители. Если их не существует, число простое. Ограничение на квадратный корень работает, потому что если число n имеет коэффициент больше √n, то оно также должно иметь соответствующий множитель меньше √n, чтобы мы могли остановиться на квадратном корне.

Быстрый рабочий пример

Возьмем число 91. Оно нечетное, не делится на 3 (9+1=10, не кратно 3) и не заканчивается на 0 или 5, поэтому все маленькие и очевидные тесты предполагают, что оно может быть простым, но проверка деления на 7 показывает точно 91 ÷ 7 = 13, поэтому 91 на самом деле является составным, с разложением простых чисел 7 × 13. Это классический пример, используемый для иллюстрации того, почему «оно не выглядит делящимся ни на что». «очевидно» — это не то же самое, что «оно простое»: единственный надежный способ узнать наверняка — это проверить каждый потенциальный делитель до квадратного корня, именно то, что этот инструмент делает автоматически и мгновенно.

Повседневное использование

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

Как пользоваться чекером

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

Простые числа бесконечны

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

Частный и мгновенный

Расчет полностью выполняется в вашем браузере, поэтому результат появляется в тот момент, когда вы вводите его, и никакое введенное вами число никогда не отправляется на какой-либо сервер, зарегистрированный или общий.