Решето Эратосфена

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

История[править | править исходный текст]

Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.

Алгоритм[править | править исходный текст]

Анимация шагов алгоритма Эратосфена для нахождения простых чисел до 120

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
  4. Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4, пока возможно.

Теперь все незачеркнутые числа в списке — простые.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[2] Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

Сложность алгоритма[править | править исходный текст]

Cложность алгоритма составляет O(n \log (\log n)) операций при составлении таблицы простых чисел до n[3].

Доказательство сложности[править | править исходный текст]

Для каждого простого p \le n будет выполняться внутренний цикл, который совершит \frac{n}{p} действий. Следовательно, нужно оценить следующую величину:

 \sum^{}_{p \le n, p\subset prime} {\frac{n}{p}} =  n*\sum^{}_{p \le n, p\subset prime} {\frac{1}{p}}

Так как количество простых чисел, меньше либо равных n, оценивается как \frac{n}{\ln n}, и, как следствие, k-е простое число примерно равно k\ln k, то сумму можно преобразовать:

 \sum^{}_{p \le n, p\subset prime} {\frac{1}{p}} \approx  \frac{1}{2} + \sum^{\frac{n}{\ln n}}_{k=2}{\frac{1}{k\ln k}}

Здесь из суммы выделено первое простое число, чтобы избежать деления на нуль. Теперь следует оценить эту сумму интегралом:

 \frac{1}{2} + \sum^{\frac{n}{\ln n}}_{k=2}{\frac{1}{k\ln k}} \approx \int\limits_2^{\frac{n}{\ln n}} {\frac{1}{k\ln k}}\,dk   =  \ln \ln \frac{n}{\ln n} \Bigr|_2^{\frac{n}{\ln n}}  = \ln \ln {\frac{n}{\ln n}} - \ln \ln 2 = \ln (\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n

В итоге получается для изначальной суммы:

 \sum^{}_{p \le n, p\subset prime} {\frac{n}{p}}  \approx \ln \ln n + o(n)

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[4].

Псевдокод[править | править исходный текст]

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде[5][6]:

Вход: натуральное число n

Пусть Aбулевый массив, индексируемый числами от 2 до n, 
изначально заполненный значениями true.

 для i := 2, 3, 4, ..., пока i2 \le n:
  если A[i] = true:
    для j := i2, i2 + i, i2 + 2i, ..., пока j \le n:
      A[j] := false

Выход: все числа i, для которых A[i] = true, являются простыми.

Примеры реализаций[править | править исходный текст]

Множество примеров реализации приведено в проекте 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;

Java[править | править исходный текст]

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;
            }
        }
    }
}

Python 2.x[править | править исходный текст]

Функция, возвращающая список простых чисел вплоть до заданного 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))

Haskell[править | править исходный текст]

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

Пример для n = 30[править | править исходный текст]

Запишем натуральные числа начиная от 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  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

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 32 = 9):

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

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 52 = 25). И т. д.

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

Необходимо провести зачёркивание кратных для всех простых чисел 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 становится невыгодным.

Уменьшение объёма потребляемой памяти[править | править исходный текст]

Алгоритм Эратосфена фактически оперирует с n битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня n переменных булевского типа не как n байт, а как n бит, то есть n/8 байт памяти.

Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять из себя несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо'льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.

Решето Эратосфена с линейным временем работы[править | править исходный текст]

Описание алгоритма: посчитать для каждого числа i от в отрезке [2; n] его минимальный простой делитель lp[i].

Кроме того, потребуется хранить список всех найденных простых чисел — для этого будет использоваться массив pr[].

Изначально все величины lp[i] заполним нулями, что означает, что все числа простые. В ходе работы алгоритма этот массив будет постепенно заполняться.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

lp[i]=0 — это означает, что число i — простое, так как для него так и не обнаружилось других делителей. Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

lp[i] \ne 0 — это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i]. В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассмотриваются числа вида:

x_j = i \cdot p_j, 

где последовательность p_j — это все простые, не превосходящие lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x_j] — очевидно, оно будет равно p_j[10].

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Никомах Герасский, Введение в арифметику, I, 13. [1]
  2. 1 2 Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, " Philosophical Transactions (1683—1775), Vol. 62. (1772), pp. 327—347.
  3. Волшебное решето Эратосфена
  4. Hardy and Wright "An Introduction to the Theory of Numbers, p. 349
  5. Algorithms in C++. — Addison-Wesley, 1992. — ISBN 0-201-51059-6, p. 16.
  6. Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
  7. Реализация метода на различных языках программирования
  8. 1 2 Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь.
  9. Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (sieve(p:xs)=p:sieve[x | x <- xs, rem x p > 0]; primes=sieve[2..])
  10. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]

Литература[править | править исходный текст]