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

Простое число n - целое число, которое не делится без остатка ни на какое целое число, кроме самого себя и 1. Другими словами, для простого числа n не существует двух целых чисел a > 1 и b > 1, чье произведение равнялось бы ему: ab = n.

Допустим, мы хотим проверить, является ли заданное число n простым. Начнем с "наивного" алгоритма поиска простых чисел (пример 6.7).

Пример 6.7. "Наивная" реализация проверки заданного числа n на простоту

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

print(prime(10)) # False
print(prime(11)) # True
print(prime(7919)) # True

Данный алгоритм проверяет, делится ли n на каждое из чисел от 2 до n-1 (1) без остатка (2). Например, при проверке на простоту числа n = 10 алгоритм быстро обнаруживает, что выражение n % i == 0 равно True при i = 2. Алгоритм нашел число i, являющееся делителем n, поэтому n не может быть простым числом. В данном случае алгоритм прерывает все дальнейшие вычисления и возвращает False.

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

Пусть нам нужно вычислить все простые числа от 2 до определенного максимального числа m. Для этого можно просто повторить проверку из примера 6.7 m-1 раз (пример 6.8). Однако вычислительные затраты при этом колоссальны.

Пример 6.8. Поиск всех простых чисел, не превышающих максимального числа m

# Поиск всех простых чисел <= m
m = 20
primes = [n for n in range(2,m+1) if prime(n)]
print(primes) # [2, 3, 5, 7, 11, 13, 17, 19]

Архив с файлом можно взять здесь.

Для создания списка всех простых чисел, не превышающих m, мы воспользовались списковым включением. Включение в алгоритм цикла for означает необходимость m вызовов функции is_prime(n), так что временная сложность ограничивается m ** 2. Количество операций растет квадратично относительно m. Поиск всех простых чисел меньше m = 100 может потребовать до m ** 2 = 10000 операций!

А теперь мы создадим однострочник, резко сокращающий подобные затраты времени.

На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание