Простые числа

Простое число имеет только два делителя: единицу и само себя. При этом единица простым числом не считается. Простые числа часто используются в программировании, так как на них основаны многие алгоритмы шифрования. Делимость чисел — это увлекательная и востребованная область математики.

Как определить, является ли введённое число простым, составным или единицей?

Для этого нужно написать функцию simple(), которая возвращает True, если число простое, и False в противном случае.

Один из самых очевидных алгоритмов проверки числа на простоту:

def simple(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Комментарии:

1. Функция simple принимает целое число и возвращает значение типа bool.
2. Если число меньше двух, оно не является простым, поэтому вернём False.
3. Организуем цикл от 2 до n − 1 и на каждом шаге будем проверять делимость n на i. Если число делится без остатка, сразу вернём False.
4. Если мы вышли из цикла, значит, число n не делится нацело ни на одно из проверенных чисел и является простым. Вернём True.

Сложность нашего алгоритма — O(n).

Не нужно считать количество делителей и сравнивать его с нулём. Если мы получили деление, это уже говорит о том, что число не простое. В функции выше мы избежали этой ошибки, но наш код всё равно не идеален. Почему?

Важно помнить, что мы работаем с целыми числами. Поэтому мы можем быть уверены: у числа n нет делителей справа от его половины (кроме самого числа). Например, если n=16, то самое большое число, на которое оно делится, — это 8. Нет смысла проверять дальше, чем n/2+1.

def simple(n):
    if n < 2:
        return False
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True

Перебор сократился, но сложность алгоритма осталась прежней, так как коэффициент 0,5 не дает значительных преимуществ для больших чисел. Как же быть?

Обрати внимание: если число n делится на i без остатка и частное равно k, то n также делится на k без остатка, ведь n = i * k. Проверяя делители по порядку, мы одновременно учитываем парные делители. Они встречаются около значения √n.

import math

def simple(n):
    if n < 2:
        return False
    limit = int(math.sqrt(n)) + 1
    for i in range(2, limit):
        if n % i == 0:
            return False
    return True

Чтобы использовать функцию вычисления корня, нам пришлось подключить библиотеку math.

Но и в этом решении есть проблема, причём довольно существенная. Мы использовали (как говорят математики) трансцендентную функцию sqrt(). Такого рода функции — например, sqrt(), sin(), cos() — работают по принципам вещественной арифметики, практически никогда не могут быть вычислены точно, да ещё и работают долго по сравнению с функциями на целых числах. Иногда без них обойтись невозможно, но не в этом случае.

Условие i ≤ √n можно записать иначе: i² ≤ n. В такой записи не нужно вычислять квадратный корень.

def simple(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

Мы снизили сложность нашего алгоритма до O(√n), и это замечательно!

Почему же важно думать об эффективности? Рассмотрим пример с большим простым числом, например, из 10 цифр. Возьмём для наглядности число около 1000000000. Старый алгоритм потребует около 500000000 шагов, в то время как новый, с корнем, — всего около 31000. Разница впечатляет.