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

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

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа 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, пока возможно.

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

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

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

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

Доказательство сложности[править | править вики-текст]

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

 \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} = n\cdot\sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{1}{p}}

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

 \sum\limits_{p \in \mathbb{P}\colon p \le n}\approx \frac{1}{2} + \sum\limits_{k=2}^{\frac{n}{\ln n}}\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\limits_{p\in \mathbb{P}\colon p \le n} {\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 - это все простые числа от 2 до n.

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

Перебор делителей[править | править вики-текст]

Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа, тестируя каждое из чисел-кандидатов с помощью перебора делителей.[7]

Широко известный функциональный код Дэвида Тёрнера 1975 года[8] часто принимают за решето Эратосфена,[7] но на самом деле это далёкий от оптимального вариант с перебором делителей.

Решето Эйлера[править | править вики-текст]

Решето Эйлера[источник не указан 129 дней] это вариант решета Эратосфена, в котором каждое составное число удаляется из списка только один раз.

Составляется исходный список начиная с числа 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)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

Решето только по нечётным числам[править | править вики-текст]

Поскольку все чётные числа, кроме 2, — составные, то можно вообще не обрабатывать никак чётные числа, а оперировать только нечётными числами. Во-первых, это позволит вдвое сократить объём требуемой памяти. Во-вторых, это уменьшит количество выполняемых алгоритмом операций (примерно вдвое).

Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но и с 3, 5, и т. д.

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

Алгоритм Эратосфена фактически оперирует с 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[9].

Псевдокод[править | править вики-текст]

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

Пусть pr - целочисленный массив, поначалу пустой;
      lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями

 для i := 2, 3, 4, ..., до n: 
   если lp[i] = 0:
       lp[i] := i
       pr[] += {i}
   для pj из pr пока pj \le lp[i]:
       lp[i*pj] := pj

Выход: все числа в массиве pr - это все простые числа от 2 до n.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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. 1 2 Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь.
  8. 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..])
  9. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]