Простые числа: почему они служат основой целочисленной арифметики
Простое число — натуральное число больше единицы, имеющее ровно два положительных делителя: единицу и само себя. Простые числа служат множителями в разложении целых чисел; их поиск, проверка простоты и распределение являются отдельными задачами теории чисел.
Простые числа
Тесты простоты
Для проверки больших чисел применяют вероятностные и детерминированные тесты, включая Миллера—Рабина и AKS. Выбор теста зависит от требуемой надёжности и вычислительных ограничений.
Решета и генерация простых
Решета позволяют эффективно находить простые числа в диапазоне и оценивать сложность генерации. На практике выбирают алгоритм в зависимости от диапазона, памяти и точности фильтрации.
Распределение простых чисел
Плотность простых уменьшается с ростом аргумента и асимптотически описывается формулой x / ln x. Анализ распределения лежит в основе решета, оценок сложности и аналитической теории чисел.
Аналитические оценки плотности
Аналитическая теория чисел описывает плотность простых через асимптотические оценки и функции распределения. Это связывает практику вычислений с фундаментальными гипотезами о распределении простых.