Как понимать результаты
В таблице ниже показаны три результата для нескольких примеров ввода.
| Ввод | Простое? | Разложение | Следующее простое |
|---|---|---|---|
| 97 | Да | 97 | 101 |
| 84 | Нет | 2 x 2 x 3 x 7 | 89 |
| 100 | Нет | 2 x 2 x 5 x 5 | 101 |
| 2 | Да (единственное чётное простое) | 2 | 3 |
| 1 | Нет (ни простое, ни составное) | - | 2 |
- Число 1 не является простым: у простого числа должно быть ровно два различных делителя, а у 1 он всего один. Исключение единицы сохраняет единственность разложения на простые множители.
- Перебор делителей даёт точный ответ, но замедляется на очень больших числах; этот калькулятор принимает числа до 10^12, где перебор проверяет делители вплоть до миллиона.
- Поиск следующего простого в этом диапазоне гарантированно завершается быстро: по постулату Бертрана между n и 2n всегда найдётся простое число.
Что такое простое число?
Простое число — это натуральное число больше 1, имеющее ровно два положительных делителя: 1 и само себя. Первые простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Число 2 — единственное чётное простое, поскольку любое другое чётное число делится на 2. Числа больше 1, не являющиеся простыми, называются составными; число 1 по определению не относится ни к простым, ни к составным.
Основная теорема арифметики утверждает, что любое целое число больше 1 представимо в виде произведения простых чисел единственным способом — с точностью до порядка сомножителей. Именно из-за этой единственности разложения простые числа называют «кирпичиками» целых чисел: 84 = 2^2 x 3 x 7, и никакая другая комбинация простых чисел в произведении не даёт 84.
Простых чисел бесконечно много — это доказал Евклид около 300 года до н. э., — и с ростом чисел они встречаются всё реже, но без какой-либо простой закономерности. Большие простые числа лежат в основе современной криптографии с открытым ключом (например, RSA), надёжность которой опирается на практическую сложность разложения произведения двух очень больших простых чисел.
Как пользоваться калькулятором простых чисел
- Введите целое число n не меньше 1. Дробные значения округляются вниз до ближайшего целого.
- Посмотрите вердикт о простоте: галочка означает, что число простое, крестик — что оно составное (или равно 1, которое не относится ни к тем, ни к другим).
- Изучите разложение на простые множители — единственное произведение простых чисел, равное вашему числу. Для простого числа разложением является само это число.
- Посмотрите следующее простое — наименьшее простое число, строго большее вашего.
Как проверяется простота: перебор делителей
Число n составное тогда и только тогда, когда у него есть делитель больше 1 и не превосходящий квадратного корня из n. Причина в том, что делители образуют пары: если n = a x b и a <= b, то a <= sqrt(n). Поэтому при переборе достаточно проверять кандидатов в делители только до sqrt(n) — а после проверки двойки нужны лишь нечётные кандидаты.
Разбор примера (простое число): n = 97. Квадратный корень из 97 равен примерно 9,85, поэтому достаточно проверить 2, 3, 5, 7 и 9. Число 97 нечётное; 9 + 7 = 16 не делится на 3; оно не оканчивается на 0 или 5; 97 / 7 = 13,857...; и 97 / 9 не даёт целого. Делителей нет, значит, 97 — простое число.
Разбор примера (разложение): n = 84. Последовательно выделяем простые множители, начиная с наименьшего: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, а 7 — простое. Итого 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Следующее простое после 84 — это 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Типичные ошибки
- Считать 1 простым числом — по определению у простого числа ровно два различных делителя, а у единицы он только один.
- Полагать, что все простые числа нечётные: 2 — простое число, и это единственное чётное простое.
- Проверять делители вплоть до самого n вместо остановки на sqrt(n) — у любого составного числа есть множитель, не превосходящий его квадратного корня.
- Считать, что все нечётные числа простые: 9 = 3 x 3, 15 = 3 x 5 и 21 = 3 x 7 — нечётные составные числа.
- Путать разложение на простые множители с любым разложением на множители: 84 = 4 x 21 — это разложение на множители, но разложение на простые множители выглядит как 2 x 2 x 3 x 7.
Часто задаваемые вопросы
Как проверить, является ли число простым?
Проверьте, делится ли число нацело на какое-либо целое от 2 до квадратного корня из него. Если ни одно не подходит, число простое. Для 97 квадратный корень равен примерно 9,85, и ни 2, ни 3, ни 5, ни 7, ни 9 не делят 97, поэтому 97 — простое. Парность делителей гарантирует, что у любого составного числа есть множитель, не превосходящий его квадратного корня.
Почему 1 не считается простым числом?
Простое число по определению имеет ровно два различных положительных делителя — 1 и само себя, а у числа 1 делитель всего один. Такое определение к тому же защищает основную теорему арифметики: будь 1 простым числом, разложения перестали бы быть единственными (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3 и так далее).
Что такое разложение на простые множители?
Это представление числа в виде произведения простых чисел, которое, согласно основной теореме арифметики, единственно с точностью до порядка сомножителей. Например, 84 = 2 x 2 x 3 x 7. Чтобы его найти, последовательно делите число на наименьшее простое, которое делит его нацело, пока частное не станет равным 1 или простым числом.
Является ли 2 простым числом?
Да — 2 простое, поскольку его делители только 1 и 2, и это единственное чётное простое число. Любое другое чётное число делится на 2 и потому составное. Именно поэтому алгоритмы проверки на простоту сначала обрабатывают двойку отдельно, а затем перебирают только нечётных кандидатов.
Сколько существует простых чисел?
Бесконечно много — это доказал Евклид около 300 года до н. э.: для любого конечного списка простых чисел число, полученное перемножением их всех и прибавлением 1, не делится ни на одно из них, значит, в списке не хватает какого-то простого числа. С ростом чисел простые встречаются всё реже — по теореме о распределении простых чисел их плотность вблизи n составляет примерно 1 / ln(n), — но никогда не исчезают.
Почему простые числа важны в криптографии?
Системы с открытым ключом, такие как RSA, опираются на асимметрию: перемножить два больших простых числа легко, а восстановить эти простые числа из их произведения при используемых на практике размерах (сотни цифр) вычислительно очень трудно. Ключи строятся именно из таких произведений, поэтому генерация простых чисел и проверка на простоту — базовые криптографические операции.
Источники
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).