에라토스테네스의 체

3. 이론적 배경

에라토스테네스의 체는 특정 수 ''x'' 이하의 소수를 찾을 때, ''x''의 제곱근 ($x^\{1/2\}$) 이하의 소수들을 미리 알고 있다면, 이 소수들의 배수를 ''x'' 이하의 정수 목록에서 제거하는 방식에 이론적 기반을 둔다. 즉, $x^\{1/2\}$ 이하 소수의 배수가 아닌 수들만 남기는 '체질' 과정을 통해 $x^\{1/2\}$보다 크고 ''x'' 이하인 소수를 결정할 수 있다는 원리이다.

이 방법의 이론적 배경에는 포함-배제의 원리가 있다. 이 원리를 적용하면 ''x'' 이하의 소수 개수 $\backslash pi(x)$에 대한 수학적 공식을 유도할 수 있다. 구체적으로, ''z'' 이하의 모든 소수의 곱을 $P=P(z)$라 하면, $\backslash sqrt\{n\}$ 이하의 소수 배수를 제외하고 남는 $\backslash sqrt\{n\}$ 초과 ''n'' 이하 소수의 개수는 뫼비우스 함수 $\backslash mu(d)$를 이용하여 다음과 같이 표현될 수 있다.

:$\backslash pi(n)-\backslash pi\; \backslash left(\backslash sqrt\{n\}\backslash ,\; \backslash right)=\backslash sum\_\{d\backslash mid\; P(\backslash sqrt\{n\})\}\; \backslash !\; \backslash mu(d)(\backslash left[\backslash frac\{\backslash ,n\backslash ,\}\{d\}\backslash right]-\backslash left[\backslash frac\{\backslash sqrt\{n\}\}\{d\}\backslash right])$

르장드르는 이를 더욱 일반화하여, 임의의 정수 집합 ''A''에서 특정 소수들의 배수를 모두 제거했을 때 남는 원소의 개수를 계산하는 공식을 제시했다. 이를 르장드르의 체라고도 부른다. ''z'' 이하의 모든 소수의 곱을 $P(z)$라고 할 때, 집합 ''A''에서 ''z'' 이하 소수의 배수를 제외하고 남은 원소의 개수 $S(A,P)$는 다음과 같이 나타낼 수 있다.

:$S(A,P)=\backslash sum\_\{d\backslash mid\; P(z)\}\backslash !\backslash mu(d)\; \backslash left|\; A\_\{d\backslash ,\}\; \backslash right|$

여기서 $A\_d$는 집합 ''A''의 원소 중에서 ''d''로 나누어 떨어지는 수들의 집합을 의미한다.

이러한 이론적 접근을 통해 소수의 분포에 관한 중요한 성질을 증명할 수 있다. 예를 들어, 위 공식을 이용하여 충분히 큰 수 ''x''에 대해 $\backslash pi(x)$의 상한을 추정하고($\backslash pi(n)\; \backslash ,\; \backslash leq\; \backslash ,\; \backslash pi(z)\; +\; n\backslash prod\_\{p\backslash leq\; z\}\; \backslash left(\; 1\; -\; \backslash frac\{1\}\{\backslash ,p\backslash ,\}\; \backslash right)\; +\; 2^\{\backslash pi(z)\}$), 결과적으로 $\backslash lim\_\{x\backslash to\; \backslash infin\}\backslash !\; \backslash frac\{\backslash ,\backslash pi\; (x)\backslash ,\}\{x\}\; =\; 0$임을 보일 수 있다. 이는 수가 커짐에 따라 전체 자연수 중에서 소수가 차지하는 비율이 점차 감소하여 0에 수렴한다는 것을 의미한다.

그러나 포함-배제의 원리에만 의존하는 방식은 소수 개수를 추정할 때 오차항($2^\{\backslash pi(z)\}$와 같은 항)이 상당히 커지는 본질적인 한계를 가진다. 이러한 어려움을 극복하고 더 정확하게 소수의 분포를 연구하기 위해 현대적인 체 방법이 개발되었다. 현대의 체 방법은 쌍둥이 소수 추측과 같은 수론 분야의 중요한 미해결 문제들을 다루는 데 핵심적인 도구로 널리 응용되고 있다.

3. 1. 수학적 원리

3. 2. 계산 복잡도

3. 3. 주요 프로그래밍 언어

3. 4. 추가 프로그래밍 언어

4. 변형 및 응용

에라토스테네스의 체는 기본적인 형태 외에도 다양한 방식으로 개선되거나 응용될 수 있다. 기본적인 개선 방법으로는 소수 ''p''의 배수를 제거할 때, ''p''의 제곱($p^2$)부터 시작하는 것이 있다. 이는 ''p''보다 작은 소수의 배수들은 이미 그 이전에 제거되었기 때문에 효율적이다.^[1] 또한, 처음부터 짝수를 제외하고 홀수만을 대상으로 하거나, 더 나아가 휠 인수분해 기법을 적용하여 초기 목록에서 2뿐만 아니라 3, 5 등 작은 소수들의 배수까지 미리 제거함으로써 계산량을 줄일 수도 있다.^[1][3][6]

에라토스테네스의 체 원리는 단순히 소수를 찾는 것을 넘어, 특정 수 이하의 소수 개수를 추정하는 데에도 응용된다. 르장드르는 포함-배제의 원리와 뫼비우스 함수 $\backslash mu(d)$를 이용하여 주어진 수 ''n'' 이하의 소수 개수($\backslash pi(n)$)를 구하는 공식을 만들었다. 이는 '르장드르의 체'라고도 불리며, 특정 수 ''z'' 이하의 모든 소수의 곱을 $P(z)$라고 할 때, 집합 ''A''에서 ''z'' 이하 소수들의 배수를 제외하고 남은 원소의 개수 $S(A,P)$는 다음과 같은 형태로 표현될 수 있다.^[5]

:$S(A,P)=\backslash sum\_\{d\backslash mid\; P(z)\}\backslash !\backslash mu(d)\; \backslash left|\; A\_\{d\backslash ,\}\; \backslash right|$

여기서 $A\_d$는 ''A''의 원소 중 ''d''로 나누어 떨어지는 것들의 집합을 의미한다. 이 공식을 이용하면 $\backslash pi(n)$의 상한을 추정할 수 있고, $\backslash lim\_\{x\backslash to\; \backslash infin\}\backslash !\; \backslash frac\{\backslash ,\backslash pi\; (x)\backslash ,\}\{x\}\; =\; 0$ 와 같은 결과를 증명할 수 있다.^[5]

하지만 르장드르의 체와 같이 포함-배제의 원리에만 의존하는 방식은 오차항이 커지는 단점이 있다. 이러한 한계를 극복하고 더 정교하게 집합의 크기를 추정하기 위해 현대적인 체 방법(sieve methods)이 개발되었다. 이 방법들은 쌍둥이 소수 추측과 같은 어려운 수론 문제들을 연구하는 데 중요한 도구로 사용되고 있다.^[5]

4. 1. 분할 체

• 크기가 Δ인 부울 배열(각 수가 소수인지 아닌지를 표시하는 배열)을 준비한다.
• 지금까지 찾은 소수들 중 ''p'' ≤ √''m'' 인 각 소수 ''p''에 대해, 현재 세그먼트(''m'' - Δ 와 ''m'' 사이) 내에 있는 ''p''의 배수들을 찾아 배열에 비소수(합성수)로 표시한다. 배수는 현재 세그먼트 내에서 ''p''의 가장 낮은 배수부터 시작하여 ''p'' 단계로 열거한다.
• 배수 표시가 끝나면, 배열에서 비소수로 표시되지 않은 위치에 해당하는 수들이 현재 세그먼트의 소수이다. 이 단계에서 새로 발견된 소수들의 배수는 고려할 필요가 없다. 왜냐하면 ''k'' ≥ 1에 대해 (''k''Δ + 1)² > (''k''+1)Δ 이므로 배수를 표시할 필요가 없기 때문이다.

4. 2. 증분 체

4. 3. 오일러의 체

• 단계 1 (p=3): 3을 소수로 식별한다. 목록의 모든 수(3, 5, 7, 9, 11, 13, 15, ...)에 3을 곱하여 (9, 15, 21, 27, 33, 39, 45, ...)를 얻고, 이들을 제거 대상으로 표시한다. 목록에서 3과 표시된 수들을 제거한다. 남은 목록은 (5, 7, 11, 13, 17, 19, 23, 25, ...)가 된다.
• 단계 2 (p=5): 5를 소수로 식별한다. 남은 목록의 모든 수(5, 7, 11, 13, 17, 19, 23, 25, ...)에 5를 곱하여 (25, 35, 55, 65, 85, 95, 115, 125, ...)를 얻고 표시한다. 목록에서 5와 표시된 수들을 제거한다. 남은 목록은 (7, 11, 13, 17, 19, 23, 29, ...)가 된다.
• 이 과정을 계속 반복한다.

참조

_[1] 논문 "''{{lang|el|Κόσκινον Ερατοσθένους}}'' or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," https://www.jstor.or[...] Philosophical Transactions 1772
_[2] 서적 Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3 https://archive.org/[...] B.G. Teubner
_[3] 서적 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 The Macmillan Company
_[4] 논문 "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications" https://www.jstor.or[...] Annals of Mathematics, Second Series 1909
_[5] 서적 Programming in Prolog
_[6] 간행물 Functional Pearl: Lazy wheel sieves and spirals of primes http://eprints.white[...]
_[7] 서적 Algorithms in C++ Addison-Wesley
_[8] 문서 An Introduction to Prime Number Sieves http://research.cs.w[...] Department of Computer Sciences University of Wisconsin-Madison 1990-01-02
_[9] 서적 Prime Numbers: A Computational Perspective Springer
_[10] 간행물 The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹²
_[11] 논문 "The pseudosquares prime sieve" https://link.springe[...] Proceedings of the 7th International Symposium on Algorithmic Number Theory 2006
_[12] 논문 "The Genuine Sieve of Eratosthenes" http://www.cs.hmc.ed[...] 2008-10-09
_[13] 문서 SASL language manual Department of Computational Science, University of St. Andrews
_[14] 뉴스 One Million Primes Through the Sieve https://archive.org/[...] BYTE 1985
_[15] 논문 "Linear prime-number sieves: a family tree," Sci. Comput. Programming 1987
_[16] 간행물 "A sublinear additive sieve for finding prime numbers" 1981
_[17] 간행물 Explaining the wheel sieve 1982
_[18] 간행물 "Fast compact prime number sieves" (among others) 1983
_[19] 간행물 A linear sieve algorithm for finding prime numbers https://ecommons.cor[...] 1978-12
_[20] 웹인용 Project Euler Problem 10 {{!}} Jason's Code Blog http://code.jasonbhi[...] 2018-03-13