Тест простоты. Алгоритмы проверки натурального числа на простоту

Тест простоты представляет собой алгоритм, который определяет, является ли заданное натуральное число простым.

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

Проверка простоты методом перебора делителей

Метод перебора делителей — это алгоритм, который проверяет простоту числа, осуществляя полный перебор всех возможных делителей.

В процессе проверки перебираются все целые (или простые) числа от 2 до квадратного корня тестируемого числа n, и вычисляется остаток от деления n на каждое из этих чисел. Если остаток от деления на какое-либо число m равен нулю, это значит, что m является делителем n, и в таком случае число n объявляется составным, после чего алгоритм прекращает свою работу. Если все возможные делители до квадратного корня из n проверены и ни один из них не является делителем, то n признаётся простым.

На практике данный алгоритм используется довольно редко из-за своей высокой асимптотической сложности, однако он оправдан для проверки небольших чисел, поскольку его реализация достаточно проста.

Проверка числа на простоту в Python

Реализуем проверку числа на простоту в виде функции, возвращающей True для простых чисел и False для составных.

Наивный алгоритм будет перебирать числа, начиная с 2, до тех пор, пока не найдёт делитель числа n. Если этот делитель равен n, значит число простое, в противном случае у n есть делитель, и оно будет составным.

Запишем алгоритм в функции `IsPrime` (где простое число на английском — prime number, а составное — composite number):

```python

def IsPrime(n):

     d = 2

     while n % d != 0:

          d += 1

     return d == n

```

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

Тем не менее, алгоритм можно оптимизировать, заметив, что любое составное число имеет делитель, не превышающий квадратного корня из самого числа. Это сокращает сложность алгоритма до O(√n):

```python

def IsPrime(n):

     d = 2

     while d * d <= n and n % d != 0:

          d += 1

     return d * d > n

```

Таким образом, алгоритм завершает работу либо при нахождении делителя, либо если проверяемый делитель превысит корень из n. Число n признается простым, если алгоритм остановился, потому что d превысил корень из n.

Перебор только нечетных делителей

Добавим ещё одну оптимизацию — будем проверять только нечетные делители, если число не делится на два:

```python

def isPrime(n):

     if n % 2 == 0:

          return n == 2

     d = 3

     while d * d <= n and n % d != 0:

          d += 2

     return d * d > n

```