최근 수정 시각 : 2024-10-13 19:28:07

에라토스테네스의 체

정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"		 공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수·배수 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론(국소체) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

파일:attachment/Erathosthenes_sieve.png
1. 개요2. 방법3. 장점4. 소스 코드5. 관련 문서

[clearfix]

1. 개요

Sieve of Eratosthenes

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 따지고 보면 [math(f \left(x\right) = \dfrac{x}{\bold{1}_{\mathbb{P}}(x)})][1]의 수열을 표로 시각화한 것이라고 볼 수 있다.

2. 방법

임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른[2] 방법이다. 예를 들어 1~144까지 숫자 중 소수를 찾는다 하자. 범위가 애매한 건 후슬할 소스코드의 이해를 돕기 위함이다. 빨간 수는 지워지는 수다.
일단 1부터 144까지 숫자를 쭉 쓴다.
1 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 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96
97 98 99 100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120
121 122 123 124 125 126 127 128 129 130 131 132
133 134 135 136 137 138 139 140 141 142 143 144
일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거하자.[3]
1 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 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96
97 98 99 100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120
121 122 123 124 125 126 127 128 129 130 131 132
133 134 135 136 137 138 139 140 141 142 143 144
2를 제외[4]한 2의 배수를 제거한다.
2 3 <colcolor=red> 4 5 <colcolor=red> 6 7 <colcolor=red> 8 9 <colcolor=red> 10 11 <colcolor=red> 12
13 <colcolor=red> 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96
97 98 99 100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120
121 122 123 124 125 126 127 128 129 130 131 132
133 134 135 136 137 138 139 140 141 142 143 144
3을 제외한 3의 배수를 제거한다.
2 3 5 7 <colcolor=red> 9 11
13 <colcolor=red> 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 81 83
85 87 89 91 93 95
97 99 101 103 105 107
109 111 113 115 117 119
121 123 125 127 129 131
133 135 137 139 141 143
4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A])
그러면 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거해야 한다.
2 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 83
85 89 91 95
97 101 103 107
109 113 115 119
121 125 127 131
133 137 139 143
6의 배수는 지울 필요 없으니(2의 배수에서 이미 지워졌다.[A]) 7을 제외한 7의 배수를 제거한다.
2 3 5 7 11
13 17 19 23
29 31
37 41 43 47
49 53 59
61 67 71
73 77 79 83
89 91
97 101 103 107
109 113 119
121 127 131
133 137 139 143
8의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A]) 9의 배수도 지울 필요 없다.(3의 배수에서 이미 지워졌다.[A]) 10의 배수도 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A]) 마지막으로 11을 제외한의 11의 배수 중 121과 143을 제거하면 다음과 같이 된다.(여기까지만 제거하는 이유는 후술한다.)
2 3 5 7 11
13 17 19 23
29 31
37 41 43 47
53 59
61 67 71
73 79 83
89
97 101 103 107
109 113
127 131
137 139

12부터는 [math(12=\sqrt {144})]이지만, 이미 2의 배수를 계산할 때 제거되었고, 이 이후는 144의 범위를 넘기 때문에 역시 지울 필요 없다.(144 이하 자연수 중에서 12의 배수는 12에 1~12사이의 값을 곱한 것인데 모두 그 사이의 배수이다.)

이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113. 127, 131,137, 139가 남는다.

이런 방법으로 만약 n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.

일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우[10] 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로[11] 에라토스테네스의 체보다 빠른 방법이 없다.[12] 프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시.

다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안 되게 빠른 방법이 넘쳐난다.

한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 [math(m=ab)]라면 [math(a)]와 [math(b)] 중 적어도 하나는 [math(\sqrt{n})]이하이다. 즉 n보다 작은 합성수 m은 [math(\sqrt{n})]보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, [math(\sqrt{n})] 이하의 수의 배수만 지우면 된다. 단적으로 1~144인 위의 경우, 사실은 11의 배수 중 남아있는 121(11*11), 143(11*13)만 더 지우면 끝난다. 만일 표에 132(169)보다 큰 수가 있다면 13를 제외한 13의 배수를 지워야 하는데, 이 과정에서 최초로 지워지는 수는 169(132)이다. 그런데 이는 주어진 범위를 초과하는 수다.

3. 장점

1부터 100까지의 수를 정말 쉬운 구구단만으로도 소수를 쉽고 빠르게 구할 수 있는 장점이 있다.

4. 소스 코드

이산수학 계통이 컴퓨터와 밀접하게 관련된 만큼, 이에 대한 소스 코드도 많다. 다음은 1부터 100만까지의 수 중 소수를 분별하는 함수를 각각 C++과 Python으로 작성한 것이다. 단, 이미 지워진 경우도 탐색하기 때문에 시간 복잡도는 [math(\mathcal{O}(n \log \log{n}))][13]이다. 특수한 방법이 사용되었는데, 자세한 내용은 합동식과 소수 정리 참고.
#!syntax cpp
#include <algorithm>
constexpr int MAX = 1000001;
bool prime[MAX];

// 일정 간격으로 특정 불린값으로 바꾸는 인라인 함수
inline void change_bool(int strt, int acc, bool flag){
    for(int i = strt; i < MAX; i += acc){
        prime[i] = flag;
    }
}

void eratosthenes(){
    std::fill_n(prime, MAX, false);//배열을 초기화한다.
    prime[2] = true;//2는 소수다.
    prime[3] = true;//3은 소수다. 이러면 5 이상의 홀수만 판별하면 된다.
    // 5 (mod 6) 과 1 (mod 6)을 참으로 설정한다. 이들은 2의배수도 아니고 3의 배수도 아닌 숫자집합이다.
    // 단, 1은 소수가 아니기에 1 (mod 6)은 7부터 시작한다.
    change_bool(5, 6, true);
    change_bool(7, 6, true);

    for (int i = 5, j = 25; j < MAX;){
        int nxt = (i - 3) % 6; // 현재의 i가 5 (mod 6) 이면 2, 1 (mod 6) 이면 4가 된다.
        if (prime[i] == true){
            int addi = i * 6; //i를 6배로 하여 x (mod 6)인 수만 검색하게 한다.

            // i * i 이상의 수를 지워나간다. 어차피 이 미만의 수들은 이미 소수 여부가 판별되었다.
            change_bool(j, addi, false);
            
            //이전 루프에서 누락된 부분을 마저 지워나간다.
            change_bool(nxt * i + j, addi, false); // nxt * i + j == i * ( i + nxt)
        }
        // 다음 루프 진행을 위한 준비. 현재의 i가 5 (mod 6) 이면 2를, 1 (mod 6)이면 4를 더한다.
        i += nxt;
        j = i * i;
    }
}


#!syntax python
def eratosthenes(num:int = 1000000):
    MAX = num + 1
    LIM = int(num ** 0.5) + 1
    RSET = lambda strt, end, gap: set(range(strt, end, gap))
    
    # 5 (mod 6)과 1 (mod 6)을 참으로 설정한다. 이들은 2의 배수도 아니고 3의 배수도 아닌 숫자집합이다.
    # 단, 1은 소수가 아니기에 1 (mod 6)은 7부터 시작한다.
    prime = RSET(5, MAX, 6) | RSET(7, MAX, 6)
    if num > 2: prime.add(3) # 3 추가
    if num > 1: prime.add(2) # 2 추가
    for i in range(5, LIM, 6):
        # 5 (mod 6) 부분
        if i in prime:
            prime -= RSET(i * i, MAX, i * 6) | RSET(i * (i + 2), MAX, i * 6)
        # 1 (mod 6) 부분
        j = i + 2
        if j in prime:
            prime -= RSET(j * j, MAX, j * 6) | RSET(j * (j + 4), MAX, j * 6)

    return prime

5. 관련 문서


[1] [math(\bold{1}_{\mathbb{P}}(x))]는 [math(x)]가 소수이면 1, 그렇지 않을 경우 0의 값을 띠는 지시함수이다. 그래서 소수가 아닌 수는 정의역에서 제외된다.[2] 변형하여 [math(\mathcal{O}(n))]의 시간 복잡도를 이룰 수 있다.[3] 그래서 기초수라고 하기도 한다.[4] 2는 1과 2(자기자신)만 약수로 가지기 때문에 2는 소수이므로 제외한다[A] 4의 케이스만 봐도 알 수 있겠지만, 이미 지워진 수는 모든 배수가 앞선 케이스에서 지워졌기 때문에 검사할 필요 없이 그냥 패스하면 된다. 즉 검사 범위가 커지면 커질수록 지워지는 숫자가 많아지기 때문에 검사 횟수가 줄어든다.[A] [A] [A] [A] [10] 예를 들어 정수 N이 주어지고 N 이하의 모든 정수를 검사해야 하는 경우. 이런 식의 문제에서 N은 다섯 자리 이상을 훌쩍 넘어가기도 하기 때문에 이런 단축 방법을 모르면 답이 없다.[11] 윌런스의 공식이 있긴 하지만 너무 비효율적이라 소수를 찾고싶으면 그냥 노가다로 나눠보든가 해야 한다. 소수 정리도 있기는 하지만 소수의 개수를 근사하는 공식이라 소수 자체를 찾는 데에는 별로 도움이 안 된다.[12] 사실 작은 범위에 대해 먼저 체를 쓴 다음 그 체로 합성수를 미리 거르는 wheel이란 기법을 쓰면 좀더 빨라지긴 한다. 대개 60을 쓴다.[13] 여기서 [math(\log)]는 이진로그다.

분류