Реализация решета Эратосфена
Простые числа — это «строительные блоки» всех чисел.
Напомним, что число является простым, если оно больше 1 и делится ТОЛЬКО на себя и на 1. Например, 2, 3, 5, 7 и 11 — это первые пять простых чисел.
Любое число, не являющееся простым, называется составным.
Предположим, нам нужно написать быстрый скрипт, вычисляющий количество простых чисел меньше 10 миллионов? Как мы могли это сделать?
Конечно, при достаточной вычислительной мощности любой скрипт будет быстрым. Мы имеем в виду, что он должен быть достаточно эффективным. Ниже приведены три сценария, каждый из которых быстрее достигает результата.
Я буду пробовать это на компьютере Mac Mini (M1 2020) 16 ГБ.
Сценарий 1: неэффективный алгоритм
Один из неэффективных способов — написать скрипт, который перебирает каждое целое число n меньше 10 миллионов и проверяет, делится ли любое целое число x (где 1‹x ≤ квадратный корень из n) на n. Если такой x существует, то n составное, иначе n простое. Где n простое, увеличить счетчик.
Почему достаточно проверить квадратный корень из n? Что ж, если n составное, то n=ab для некоторых целых чисел a, b, где a›1 и b›1. Однако a и b не могут оба быть больше квадратного корня из n, иначе ab›n, что является противоречием. Это означает, что либо a, либо b меньше или равно квадратному корню из n.
Вот скрипт Python для вычисления количества простых чисел меньше 10 миллионов. Я использовал декораторы Python, чтобы определить, сколько времени это займет:
import time
from math import isqrt
def timer(func):
def wrapper(*args, **kwargs):
before = time.time()
result = func(*args, **kwargs)
print('Function took:', time.time() - before, " seconds")
return result
return wrapper
@timer
def get_number_of_primes_less_than(upper_bound):
counter = 0
for n in range(2,upper_bound):
flag = True
for x in range(2, isqrt(n)+1):
if n!=x and n % x==0:
flag = False
break
if flag:
counter += 1
return counter
print(get_number_of_primes_less_than(10000000))
Потребовалось 126 секунд, чтобы вычислить, что существует 664 579 простых чисел, меньших 10 миллионов.
Сценарий 2: неэффективный алгоритм (улучшенный)
Очевидная проблема со сценарием 1 выше — это количество расточительных операций.
Например, при проверке того, является ли 25 простым, он увидит, что 25 не делится на 2, но затем без необходимости проверит, делится ли 25 на 4, чего не может быть, поскольку в противном случае оно делилось бы на 2.
Один из способов улучшить это — вести список простых чисел по ходу работы и проверять только, делится ли наше n на числа в списке простых чисел.
Вот улучшенный скрипт:
import time
from math import isqrt
def timer(func):
def wrapper(*args, **kwargs):
before = time.time()
result = func(*args, **kwargs)
print('Function took:', time.time() - before, " seconds")
return result
return wrapper
@timer
def get_number_of_primes_less_than_improved(upper_bound):
counter = 0
primes = [2]
for n in range(3,upper_bound):
flag = True
for x in primes:
if x > isqrt(n):
break
if n % x == 0:
flag = False
break
if flag:
primes.append(n)
return len(primes)
print(get_number_of_primes_less_than_improved(10000000))
Это заняло 33 секунды, чтобы получить результат. Все быстрее!
Сценарий 3: Решето Эратосфена
Решето Эратосфена — это древний алгоритм, который можно использовать для определения количества простых чисел, меньших целого числа N. Он упоминается еще в Древней Греции, как Эратосфен из Кирены.
Это работает следующим образом: мы берем 2 как простое и вычеркиваем каждое кратное 2 меньше N. Затем мы проверяем следующее наибольшее число после 2, которое не вычеркнуто, это 3, которое тогда является простым. Затем мы скрещиваем каждое число, кратное 3. Следующим не вычеркнутым числом будет 5, которое тогда будет простым, и так далее…
Вот анимированное изображение, которое иллюстрирует эту концепцию и вычисляет простые числа меньше 120:
Ниже приведена реализация этого алгоритма, в которой снова используются декораторы Python для определения того, сколько времени это займет:
import time
from math import isqrt
def timer(func):
def wrapper(*args, **kwargs):
before = time.time()
result = func(*args, **kwargs)
print('Function took:', time.time() - before, " seconds")
return result
return wrapper
@timer
def sieve_of_eratosthenes(upper_bound):
primes = [True] * upper_bound
primes[0] = False
primes[1] = False
for i in range(2, isqrt(upper_bound)+1):
if primes[i]:
for x in range(i*i, upper_bound, i):
primes[x]=False
return primes.count(True)
print(sieve_of_eratosthenes(10000000))
Основная идея здесь состоит в том, чтобы объявить массив размером 10 миллионов со всеми значениями, помеченными как True. Используя описанный выше подход, начните отмечать числа, которые не являются простыми, как False.
Примечание. Для переменных primes[0] и primes[1] вручную устанавливается значение False, поскольку 0 и 1 не являются простыми по определению.
В этом скрипте есть два своеобразных твика оптимизации:
- Переменная i увеличивается только до целых чисел, меньших или равных квадратному корню из n.
- Переменная x, которая используется для обозначения чисел в массиве, которые не являются простыми, так как False начинается с i*i, а не с i+i.
Читателю остается в качестве упражнения выяснить, почему эти настройки работают. Совет: Используя ручку и бумагу, попробуйте самостоятельно запустить алгоритм с низким значением n.
Это заняло 1,57 секунды, чтобы получить результат. Теперь мы говорим!
Заключительные замечания
Это ни в коем случае не самый эффективный способ сделать это. Одна из проблем этого последнего подхода заключается в том, что для очень больших N создание огромных массивов требует большого объема памяти.
Алгоритм решета Эратосфена требует O(N log (log N)) времени, чтобы найти все простые числа, меньшие N.
** Рассмотрите возможность членства в Medium с моей реферальной ссылкой здесь. Вы будете поддерживать мое письмо, и с вас не будет никаких дополнительных затрат. Кроме того, вы можете купить мне кофе ниже. Большое спасибо!***
