Проверяет, простое ли число, раскладывает его на простые множители и находит все делители. Работает с числами до 10¹⁵ — быстрее, чем перебор в столбик.
Поддерживаются натуральные числа до 999 999 999 999 999.
Простое число делится без остатка только на единицу и на себя. Наименьшее простое — 2, и это единственное чётное простое число. Единица не считается ни простой, ни составной: если бы её признали простой, разложение на множители перестало бы быть единственным.
Любое натуральное число больше единицы разлагается на простые множители единственным способом — с точностью до порядка. Именно на этом свойстве держится вся теория чисел, а вместе с ней и современная криптография: перемножить два больших простых числа легко, а разложить их произведение обратно — вычислительно очень трудно.
Например, для проверки числа 97 хватит делителей до 9: это 2, 3, 5 и 7. Ни один не подходит — значит, 97 простое.
Бесконечно много — это доказал Евклид ещё в III веке до нашей эры. При этом простые числа встречаются всё реже: среди первых сотни их 25, а среди чисел от миллиона до миллиона ста — уже около 7.
φ(n) — количество чисел от 1 до n, взаимно простых с n. Для простого числа p она равна p−1. Функция Эйлера лежит в основе алгоритма шифрования RSA.
Шифрование данных, хеш-таблицы, генераторы случайных чисел, контрольные суммы. Когда ваш браузер устанавливает защищённое соединение, он использует свойства больших простых чисел.