20-07-2023
Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.
Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
Теперь все незачеркнутые числа в списке — это все простые числа от 2 до n.
На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[2] Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.
Cложность алгоритма составляет операций при составлении таблицы простых чисел до [3].
Для каждого простого будет выполняться внутренний цикл, который совершит действий. Следовательно, нужно оценить следующую величину:
=
Так как количество простых чисел, меньше либо равных , оценивается как , и, как следствие, -е простое число примерно равно , то сумму можно преобразовать:
Здесь из суммы выделено первое простое число, чтобы избежать деления на нуль. Теперь следует оценить эту сумму интегралом:
В итоге получается для изначальной суммы:
Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[4].
Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде[5][6]:
Вход: натуральное число n Пусть A — булевый массив, индексируемый числами от 2 до n, изначально заполненный значениями true. для i := 2, 3, 4, ..., пока i2 n: если A[i] = true: для j := i2, i2 + i, i2 + 2i, ..., пока j n: A[j] := false Выход: числа i, для которых A[i] = true - это все простые числа от 2 до n.
Множество примеров реализации приведено в проекте rosettacode.org[7]. В данном разделе приводится несколько примеров на популярных языках программирования.
int n; vector<bool> prime (n+1, true); prime[0] = prime[1] = false; for (int i=2; i*i<=n; ++i) // valid for n < 46340^2 = 2147395600 if (prime[i]) for (int j=i*i; j<=n; j+=i) prime[j] = false;
import java.util.Arrays; int n; boolean[] primes=new boolean[n]; public void fillSieve() { Arrays.fill(primes,true); primes[0]=primes[1]=false; for (int i=2;i<primes.length;i++) { if(primes[i]) { for (int j=2;i*j<primes.length;j++) { primes[i*j]=false; } } } }
Функция, возвращающая список простых чисел вплоть до заданного n:
def eratosthenes(n): multiples = [] for i in xrange(2, n+1): if i not in multiples: print i multiples.extend(xrange(i*i, n+1, i))
primesTo n = eratos [2..n] where eratos [] = [] eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..n]) minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs
Запишем натуральные числа начиная от 2 до 30 в ряд:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 22 = 4):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 32 = 9):
2 3456789101112131415161718192021222324252627282930
Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 52 = 25). И т. д.
2 3456789101112131415161718192021222324252627282930
Необходимо провести зачёркивание кратных для всех простых чисел p, для которых p2 ≤ n. В результате все составные числа будут зачеркнуты, а незачеркнутыми останутся все простые числа.
Для n = 30 уже после зачёркивания кратных числу 5 все составные числа получаются зачеркнутыми:
2 3 5 7 11 13 17 19 23 29
В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p)[2]. Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.
Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа, тестируя каждое из чисел-кандидатов с помощью перебора делителей.[8]
Широко известный функциональный код Дэвида Тёрнера 1975 года[9] часто принимают за решето Эратосфена,[8] но на самом деле это далёкий от оптимального вариант с перебором делителей.
Решето Эйлера это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.
Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, и определяются его произведения на каждое число в списке которые маркируются для последуюшего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:
[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ... [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]
Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.
Примерная реализация на языке Хаскелл:
primesToEU n = eulers [2..n] where eulers [] = [] eulers (p:xs) = p : eulers (xs `minus` takeWhile (<= n) (map (p*) (p:xs))) -- eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..n])
Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит число делаемых алгоритмом операций примерно вдвое.
Это можно обобщить на числа взаимно простые не только с 2 (т.е. нечетные числа), но и с 3, 5, и т.д.. Использование простых чисел свыше 7 или 11 становится невыгодным.
Алгоритм Эратосфена фактически оперирует с битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня переменных булевского типа не как байт, а как бит, то есть байт памяти.
Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять из себя несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо'льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.
Описание алгоритма: посчитать для каждого числа от в отрезке его минимальный простой делитель .
Кроме того, потребуется хранить список всех найденных простых чисел — для этого будет использоваться массив .
Изначально все величины заполним нулями, что означает, что все числа простые. В ходе работы алгоритма этот массив будет постепенно заполняться.
Дальше следует перебрать текущее число от 2 до . Здесь может быть два случая:
— это означает, что число — простое, так как для него так и не обнаружилось других делителей. Следовательно, надо присвоить и добавить в конец списка .
— это означает, что текущее число — составное, и его минимальным простым делителем является . В обоих случаях дальше начинается процесс расстановки значений в массиве : следует брать числа, кратные , и обновлять у них значение . Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение было бы установлено не более одного раза.
Утверждается, что для этого можно поступить таким образом. Рассмотриваются числа вида:
где последовательность — это все простые, не превосходящие (как раз для этого понадобилось хранить список всех простых чисел).
У всех чисел такого вида проставим новое значение — очевидно, оно будет равно [10].
sieve(p:xs)=p:sieve[x | x <- xs, rem x p > 0]; primes=sieve[2..]
)Эратосфена решето.