Узнайте, как определить, является ли число простым или составным. Изучение свойств простых чисел, метод теста Миллера-Рабина, решето Эратосфена и решето Аткина.
Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p.
Пример: число 2 простое (делится на 1 и на 2), а 4 не является простым, так как, помимо 1 и 4, делится на 2 — имеет три натуральных делителя.
Изучением свойств простых чисел занимается теория чисел, а основная теорема арифметики устанавливает в ней их центральную роль: любое целое число, превышающее 1, либо является простым, либо может быть выражено произведением простых чисел, причём такое представление однозначно с точностью до порядка сомножителей. Единицу не относят к простым числам, так как иначе указанное разложение становится неоднозначным: x = 1⋅x = 1⋅1⋅x = 1⋅1⋅...⋅1⋅x.
Натуральные числа можно разделить на три класса: единица (имеет один натуральный делитель), простое число (имеет два натуральных делителя), составное число (имеет более двух натуральных делителей). Как простых, так и составных чисел бесконечно много.
Метод теста Миллера-Рабина
Для определения простого числа можно использовать метод теста Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах, так как обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма.
Суть метода заключается в следующем: случайным образом выбираются значения a и проводятся вычисления с использованием формулы a^d mod n, где d и n являются целыми числами. Если результат вычисления не равен 1 и не равен n-1, то число n не является простым. Если же результат равен 1 или равен n-1, то число n может быть простым с высокой долей уверенности.
Для достижения более точного результата, проводятся вычисления для нескольких различных значений a. Если для всех значений тест дает положительный результат, можно с достаточно высокой долей уверенности считать, что число n является простым.
Решето Эратосфена
Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном, который позволяет найти все простые числа меньше заданного числа n.
Суть метода заключается в следующем:
- Возьмем набор чисел от 2 до n.
- Вычеркнем из набора все числа, делящиеся на 2, кроме самого числа 2.
- Перейдем к следующему "не вычеркнутому" числу — 3, и вычеркнем все числа, делящиеся на 3.
- Продолжим этот процесс для оставшихся чисел, вычеркивая все числа, делящиеся на них.
- После выполнения этих действий, в исходном списке останутся только простые числа.
Алгоритм можно оптимизировать, останавливаясь после вычеркивания чисел, делящихся на квадратный корень из n. Это позволяет снизить сложность алгоритма.
Существуют также некоторые оптимизации, такие как использование wheel factorization (включение в изначальный список только чисел, взаимно простых с несколькими первыми простыми числами) и сегментирование (разделение набора чисел на сегменты и применение решета Эратосфена отдельно для каждого сегмента).
См. также
Решето Аткина
Более совершенным алгоритмом отсеивания составных чисел является решето Аткина, предложенное Аткином и Берштайном.
Решето Аткина основано на трех свойствах простых чисел:
- Если n — положительное число, не кратное квадрату простого числа, и число корней уравнения x^2 mod n равно 1, то n — простое.
- Если n — положительное число, кратное четырем, и число корней уравнения 4x^2 mod n равно 1, то n — простое.
- Если n — положительное число, не кратное двум и трем, и число корней уравнения 3x^2 mod n равно 1, а число корней уравнения 4x^2 mod n равно 1, то n — простое.
Решето Аткина позволяет более эффективно находить простые числа, чем решето Эратосфена.
Использование этих методов поможет определить, является ли число простым или составным с высокой долей уверенности.
Что нам скажет Википедия?
Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p.
Пример: число 2 простое (делится на 1 и на 2), а 4 не является простым, так как, помимо 1 и 4, делится на 2 — имеет три натуральных делителя.
Изучением свойств простых чисел занимается теория чисел, а основная теорема арифметики устанавливает в ней их центральную роль: любое целое число, превышающее 1, либо является простым, либо может быть выражено произведением простых чисел, причём такое представление однозначно с точностью до порядка сомножителей. Единицу не относят к простым числам, так как иначе указанное разложение становится неоднозначным: x = 1⋅x = 1⋅1⋅x = 1⋅1⋅...⋅1⋅x.
Натуральные числа можно разделить на три класса: единица (имеет один натуральный делитель), простое число (имеет два натуральных делителя), составное число (имеет более двух натуральных делителей). Как простых, так и составных чисел бесконечно много.
