Sieve of Eratosthenes

수학(mathematics)에서, 에라토스테네스의 체(sieve of Eratosthenes)는 주어진 한계까지 모든 소수(prime numbers)를 찾기 위한 고대 알고리듬(algorithm)입니다.

그것은 첫 번째 소수 2부터 시작하여 각 소수의 배수를 합성수(composite, 즉, 소수가 아님)로 반복적으로 표시함으로써 수행합니다. 주어진 소수의 배수는 해당 소수와 같은 그들 사이의 상수 차이를 갖는 해당 소수에서 시작하는 숫자의 순서열로 생성됩니다.^[1] 이것은 시행 나눗셈(trial division)을 사용하여 각 후보 번호를 각 소수에 의한 나눔가능성에 대해 순차적으로 테스트하는 것과 체의 주요 차이점입니다.^[2] 일단 발견된 각 소수의 모든 배수가 합성수로 표시되면, 남아있는 표시되지 않은 숫자는 소수입니다.

체에 대한 최초의 알려진 참조 (Ancient Greek: κόσκινον Ἐρατοσθένους kóskinon Eratosthénous)는 2세기 초 게라사의 니코마코스(Nicomachus of Gerasa)의 Introduction to Arithmetic에 있으며,^[3] 이는, 비록 소수 대신 홀수로 체질을 설명하지만, 기원전 3세기 그리스 수학자, 싸이리니의 에라토스테네스(Eratosthenes of Cyrene)에게 귀속됩니다.^[4]

그것은 많은 소수 체(prime number sieves) 중 하나이며, 더 작은 소수를 모두 찾는 가장 효율적인 방법 중 하나입니다. 그것은 산술 진행(arithmetic progressions)에서 소수를 찾기 위해 사용될 수 있습니다.^[5]

Overview

Sift the Two's and Sift the Three's:
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Anonymous^[6]

소수(prime number)는 정확히 두 개의 다른 자연수 약수(divisors): 숫자 1과 자기 자신을 가지는 자연수입니다.

에라토스테네스의 방법으로 주어진 정수 $n$ 보다 작거나 같은 모든 소수를 찾기 위해:

2에서 까지의 연속 정수 목록: $(2, 3, 4, ..., n)$ 을 만듭니다.
처음에, $p$ 를 가장 작은 소수, 2와 같다고 놓습니다.
$2 p$ 에서 $n$ 까지 $p$ 의 증가분을 셈으로써 $p$ 의 배수를 열거하고, 목록에서 표시합니다 (이것들은 $2 p, 3 p, 4 p, ...$ 일 것입니다; $p$ 자체는 표시하면 안 됩니다).
표시되지 않은 $p$ 보다 큰 목록에서 가장 작은 수를 찾습니다. 만약 그러한 숫자가 없으면 중지합니다. 그렇지 않으면, 이제 $p$ 를 이 새로운 숫자 (다음 소수)와 같게 놓고, 3단계부터 반복합니다.
알고리듬이 종료할 때, 목록에 표시되지 않은 남아있는 숫자는 $n$ 아래의 모든 소수입니다.

여기서 주요 아이디어는 $p$ 에 주어진 모든 각 값이 소수가 될 것이라는 것인데, 왜냐하면 그것이 합성수이면 어떤 다른 더 작은 소수의 배수로 표시되기 때문입니다. 일부 숫자는 두 번 이상 표시될 수 있습니다 (예를 들어, 15는 3과 5 모두에 표시될 것입니다).

하나의 개선점으로, $p 2$ 부터 시작하여 3단계에서 숫자를 표시하는 것으로 충분한데, 왜냐하면 $p$ 의 모든 더 작은 배수는 해당 지점에서 이미 표시되었기 때문입니다. 이것은 $p 2$ 이 $n$ 보다 클 때 알고리듬이 4단계에서 종료될 수 있음을 의미합니다.^[1]

또 다른 개선점은 처음에 홀수만 나열 $(3, 5, ..., n)$ 하고, 3단계에서 $2 p$ 의 증가분에서 세어서, $p$ 의 홀수 배수만 표시하는 것입니다. 이것은 실제로 원래 알고리듬에 나타납니다.^[1]^[4] 이것은 바퀴 인수분해(wheel factorization)로 일반화될 수 있으며, 홀수 (즉, 2와 서로소인 숫자)뿐만 아니라 처음 몇 개에서 소수와 서로소(coprime)인 숫자로만 초기 목록을 형성하고, 그러한 $p$ 의 배수만 최초 위치에서 그것들의 작은 소수와 서로소인 것을 생성하도록 해당하는 조정된 증분에서 셉니다.^[7]

Example

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에서 2의 증가분으로 셈으로써 2 뒤의 목록에서 두 번째 숫자마다 줄을 긋습니다 (이들은 목록에서 2의 배수가 될 것입니다):

 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 다음에 오는 숫자는 3입니다; 3에서 3의 증가분에서 셈으로써 3 뒤의 목록에서 세 번째 숫자마다 줄을 긋습니다 (이것들은 목록에서 3의 배수가 될 것입니다):

 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 다음으로 아직 줄이 그어지지 않은 다음 숫자는 5입니다; 5부터 5의 증가분 (즉, 모든 5의 배수)에서 셈으로써 5 뒤의 목록에서 5번째 숫자마다 줄을 긋습니다:

 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 다음으로 아직 줄이 그어지지 않은 다음 숫자는 7입니다; 다음 단계는 목록에서 7 뒤의 모든 7번째 숫자를 지우는 것이지만, 그것들은 이들 숫자 (14, 21, 28)도 7 × 7이 30보다 더 크기 때문에 더 작은 소수의 배수이기 때문에 이 시점에서 이미 모두 지워졌습니다. 목록에서 이 시점에서 줄이 그어지지 않은 숫자는 모두 30 아래의 소수입니다:

 2  3     5     7          11    13          17    19          23                29

Algorithm and variants

Pseudocode

에라토스테네스의 체는 다음과 같이 유사-코드로 표현될 수 있습니다:^[8]^[9]

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding  $\sqrt n$  do
        if A[i] is true
            for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

이 알고리듬은 $n$ 보다 크지 않은 모든 소수를 생성합니다. 그것은 $i 2$ 에서 각 소수 $i$ 의 배수를 열거하는 것으로 시작하는 공통 최적화를 포함합니다. 이 알고리듬의 시간 복잡도(time complexity)는 보통 그렇듯이 배열 업데이트가 $O (1)$ 연산이라는 조건으로 하여 $O (n log log n)$ 입니다.^[9]

Segmented sieve

소렌슨(Sorenson)이 언급한 것처럼, 에라토스테네스의 체에 관한 문제는 수행하는 연산의 수가 아니라 오히려 메모리 요구 사항입니다.^[9] 큰 $n$ 에 대해, 소수의 범위가 메모리에 맞지 않을 수 있습니다; 더 나쁘게, 심지어 보통 $n$ 에 대해, 그것의 캐시(cache) 사용이 매우 차선책이라는 것입니다. 그 알고리듬은 전체 배열 $A$ 를 통과하며, 거의 참조의 지역성(locality of reference)을 나타내지 않습니다.

이들 문제에 대한 해결책은 한 번에 범위의 일부만 체질하는 분할된(segmented) 체에 의해 제공됩니다.^[10] 이것들은 1970년대부터 알려져 왔고, 다음과 같이 작동합니다:^[9]^[11]

2에서 $n$ 까지의 범위를 $\Delta \leq {\sqrt {n}}$ 크기의 분절로 나눕니다.
정규 체를 사용하여 첫 번째 (즉, 가장 낮은) 분절에서 소수를 찾습니다.
다음 분절 각각에 대해, m이 분절의 최상위 값을 갖는 증가하는 순서에서 다음과 같이 소수를 찾습니다:
1. 크기 $Δ$ 의 부울 배열을 설정합니다, 그리고
2. $m - Δ$ 와 $m$ 사이에서 $p$ 의 가장 낮은 배수를 계산하고, 보통과 같이 $p$ 의 단계에서 그 배수를 열거함으로써, 지금까지 찾은 각 소수 $p\leq {\sqrt {m}}$ 의 배수에 해당하는 배열에서 위치를 비-소수로 표시합니다. 분절에서 소수의 제곱은 분절에 있지 않기 때문에 ( $k \geq 1$ 에 대해, $(k\Delta +1)^{2}>(k+1)\Delta$ 를 가짐) 남아있는 위치는 분절에서 소수에 해당합니다.

만약 $Δ$ 가 ${\sqrt {n}}$ 으로 선택되면, 알고리듬의 공간 복잡도는 $O{\sqrt {n}}$ 이고, 반면에 시간 복잡도는 정규 체의 그것과 같습니다.^[9]

위쪽 한계 $n$ 이 너무 커서 에라토스테네스의 페이지 분할된 체에서 요구하는 ${\sqrt {n}}$ 아래의 체질 소수가 메모리에 맞지 않는 범위에 대해, 소렌슨의 체(sieve of Sorenson)와 같이 느리지만 훨씬 더 공간-효율적인 체는 대신 사용될 수 있습니다.^[12]

Incremental sieve

체의 증분 형식화는^[2] (소수가 배수 사이의 틈에서 발견될 수 있도록) 소수 생성을 그것들의 배수 생성과 인터리브함으로써 소수를 무한정 (즉, 위쪽 경계 없이) 생성하며, 여기서 각 소수 $p$ 의 배수는 소수의 제곱으로부터 $p$ (또는 홀수 소수에 대해 $2 p$ )의 증분에서 셈으로써 직접 생성됩니다. 생성은 소수의 제곱이 효율성에 악영향을 미치지 않도록 도달될 때까지만 시작되어야 합니다. 그것은 데이터-흐름(dataflow) 패러다임에서 다음과 같이 기호적으로 표현될 수 있습니다:

primes = [2, 3, ...] \ [[p², p²+p, ...] for p in primes],

이때 숫자의 산술 진행(arithmetic progressions)의 집합 뺄셈(set subtraction)을 나타내는 \와 함께 목록 이해(list comprehension) 표기법을 사용합니다.

소수는 역시 한 번에 하나의 소수, 순차적인 소수에 의해 나눔가능성 테스트(divisibility testing)를 통해 합성수를 반복적으로 체질함으로써 생산될 수 있습니다. 그것은 에라토스테네스의 체는 아니지만, 비록 에라토스테네스의 체가 합성수를 테스트하는 대신 직접 생성할지라도 종종 혼동됩니다. 시행 나눗셈은 소수의 범위를 생성하는 데 있어 에라토스테네스의 체의 그것보다 더 나쁜 이론적 복잡성(complexity)을 가집니다.^[2]

각각의 소수를 테스트할 때, 최적의 시행 나눗셈 알고리듬은 그것의 제곱근을 초과하지 않는 모든 소수를 사용하고, 반면에 에라토스테네스의 체는 그것의 소인수에서만 각 합성수를 생성하고, 합성수 사이에서 "무료"로 소수를 얻습니다. 널리 알려진 1975년 David Turner에 의한 함수형(functional) 체 코드는^[13] 종종 에라토스테네스의 체의 예제로 제시되지만^[7] 실제로는 부분-최적의 시행 나눗셈 체입니다.^[2]

Algorithmic complexity

에라토스테네스의 체는 컴퓨터 성능을 벤치마킹하는 데 널리 사용되는 방법입니다.^[14] 확률 접근 기계(random access machine) 모델에서 $n$ 아래의 모든 소수를 계산하는 시간 복잡도(time complexity)는 $O (n log log n)$ 연산이며, 소수 조화 급수(prime harmonic series)가 $log log n$ 에 점근적으로 접근한다는 사실의 직접적인 결과입니다. 그러나, 그것은 입력 크기와 관련하여 지수적 시간 복잡도를 가지며, 이는 그것을 유사-다항식(pseudo-polynomial) 알고리듬으로 만듭니다. 기본 알고리듬은 $O (n)$ 의 메모리를 요구합니다.

알고리듬의 비트 복잡도( bit complexity)는 $O (n)$ 의 메모리 요구 사항을 갖는 $O (n (log n) (log log n))$ 비트 연산입니다.^[15]

통상적으로 구현된 페이지 분할된 버전은 비-분할된 버전과 같은 $O (n log log n)$ 의 연산적 복잡성을 가지지만 공간 요구 사항을 분절 페이지의 가장 최소 크기 더하기 크기 $O (\sqrt n / log n)$ 의 연속 페이지 분절로부터 합성수를 추려내는 데 사용되는 범위의 제곱근보다 작은 기본 소수를 저장하는 데 필요한 메모리로 줄입니다.

기본 최적화를 갖는 에라토스테네스의 체의 특수한 (드물게 구현된) 분절된 버전은 $O (n)$ 연산과 $O (\sqrt n log log n / log n)$ 비트의 메모리를 사용합니다.^[16]^[17]^[18]

큰 O 표기법(big O notation)을 사용하면 실제 범위에서 매우 중요할 수 있는 상수 인자와 오프셋을 무시합니다: 프리처드 바퀴 체로 알려진 에라토스테네스의 체 변형은 $O (n)$ 성능을 가지지만, 그것의 기본 구현은^[16]^[17]^[18] 사용-가능한 범위를 사용 가능한 메모리 양으로 제한하는 "하나의 큰 배열" 알고리듬을 요구하거나 메모리 사용을 줄이기 위해 페이지를 분할해야 합니다. 메모리를 절약하기 위해 페이지 분할로 구현될 때, 기본 알고리듬은 여전히 약 $O (n / log n)$ 비트의 메모리를 필요로 합니다 ( $O (\sqrt n / log n)$ 의 메모리 비트를 사용하는 에라토스테네스의 기본 페이지 분할 체의 요구 사항보다 훨씬 더 많은 것입니다). 프리처드의 연구는 큰 상수 인수를 희생하여 메모리 요구 사항을 줄였습니다. 비록 결과 바퀴 체는 $O (n)$ 성능과 허용 가능한 메모리 요구 사항을 가지지만, 실용적인 체질 범위에 대해 합리적으로 바퀴 인수화된(Wheel Factorized) 기본 에라토스테네스의 체보다 빠르지 않습니다.

Euler's sieve

오일러의 제타 곱 공식의 증명(proof of the zeta product formula)은 각 합성수가 정확히 한 번 제거되는 에라토스테네스의 체의 버전을 포함하고 있습니다.^[9] 같은 체는 재발견되었고 Gries & Misra (1978)에 의해 선형 시간이 걸리는 것으로 관찰되었습니다.^[19] 그것도 2에서 n까지의 숫자 목록을 순서대로 나열하는 것으로 시작합니다. 각 단계에서 첫 번째 원소는 다음 소수로 식별되고, 목록의 각 원소와 곱해지고 (따라서 자체로 시작), 결과는 후속 삭제를 위해 목록에 표시됩니다. 초기 원소와 표시된 원소가 그런-다음 작업하는 순서에서 제거되고, 과정이 반복됩니다:

 [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 소수와 서로소인 숫자만 포함할 것입니다 (비고, 바퀴 인수분해).

따라서, 경계진 소수 순서열을 생성할 때, 그 다음 식별된 소수가 위쪽 극한의 제곱근을 초과할 때, 목록에서 모든 남아있는 숫자가 소수입니다.^[9] 위에 주어진 예에서 그것은 11을 다음 소수로 식별하여 달성되며, 80보다 작거나 같은 모든 소수의 목록을 제공합니다.

단계에서 버릴 숫자는 해당 단계에서 배수를 표시하는 동안 계속 사용됩니다. 예를 들어, 3의 배수는 3 × 3 = 9, 3 × 5 = 15, 3 × 7 = 21, 3 × 9 = 27, ..., 3 × 15 = 45이므로 이것을 주의해서 다루어야 합니다.

References

^ ^a ^b ^c 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.
^ ^a ^b ^c ^d O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).
^ Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30
^ ^a ^b Nicomachus of Gerasa (1926), Introduction to Arithmetic; translated into English by Martin Luther D'Ooge ; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3, New York: The Macmillan Company, p. 204
^ J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.
^ Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. ISBN 3-540-11046-1.
^ ^a ^b Runciman, Colin (1997). "Functional Pearl: Lazy wheel sieves and spirals of primes" (PDF). Journal of Functional Programming. 7 (2): 219–225. doi:10.1017/S0956796897002670. S2CID 2422563.
^ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.
^ ^a ^b ^c ^d ^e ^f ^g 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).
^ Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.
^ Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹²". BIT. 17 (2): 121–127. doi:10.1007/BF01932283. S2CID 122592488.
^ J. Sorenson, "The pseudosquares prime sieve", Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
^ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0). But see also Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976, where we find the following, attributed to P. Quarendon: primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]; the priority is unclear.
^ Peng, T. A. (Fall 1985). "One Million Primes Through the Sieve". BYTE. pp. 243–244. Retrieved 19 March 2016.
^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
^ ^a ^b Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. MR600730
^ ^a ^b Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR685983
^ ^a ^b Paul Pritchard, "Fast compact prime number sieves" (among others), Journal of Algorithms 4 (1983), 332–344. MR729229
^ Gries, David; Misra, Jayadev (December 1978), "A linear sieve algorithm for finding prime numbers" (PDF), Communications of the ACM, 21 (12): 999–1003, doi:10.1145/359657.359660, hdl:1813/6407, S2CID 11990373.

External links

primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes
Eratosthenes, sieve of at Encyclopaedia of Mathematics
Interactive JavaScript Page
Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
Sieve of Eratosthenes in Haskell
Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
A related sieve written in x86 assembly language
Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C
SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.

[horsley-1] 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.

[ONeill-2] O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).

[nicomachus-3] Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30

[nicomachus1926-4] Nicomachus of Gerasa (1926), Introduction to Arithmetic; translated into English by Martin Luther D'Ooge ; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3, New York: The Macmillan Company, p. 204

[5] J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.

[6] Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. ISBN 3-540-11046-1.

[Runciman-7] Runciman, Colin (1997). "Functional Pearl: Lazy wheel sieves and spirals of primes" (PDF). Journal of Functional Programming. 7 (2): 219–225. doi:10.1017/S0956796897002670. S2CID 2422563.

[sedgewick-8] Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.

[intro-9] ^ ^a ^b ^c ^d ^e ^f ^g 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).

[10] Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.

[11] Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹²". BIT. 17 (2): 121–127. doi:10.1007/BF01932283. S2CID 122592488.

[12] J. Sorenson, "The pseudosquares prime sieve", Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).

[13] Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0). But see also Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976, where we find the following, attributed to P. Quarendon: primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]; the priority is unclear.

[peng1985fall-14] Peng, T. A. (Fall 1985). "One Million Primes Through the Sieve". BYTE. pp. 243–244. Retrieved 19 March 2016.

[15] Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.

[Pritchard1-16] Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. MR600730

[Pritchard2-17] Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR685983

[Pritchard3-18] Paul Pritchard, "Fast compact prime number sieves" (among others), Journal of Algorithms 4 (1983), 332–344. MR729229

[19] Gries, David; Misra, Jayadev (December 1978), "A linear sieve algorithm for finding prime numbers" (PDF), Communications of the ACM, 21 (12): 999–1003, doi:10.1145/359657.359660, hdl:1813/6407, S2CID 11990373.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]