[Algorithm] 에라토스테네스의 체

에라토스테네스의 체 란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

단일 숫자 소수 여부 확인

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

에라토스테네스의 체 구현하기

#include <stdio.h>

int number = 100000;
int a[1000001];

void primeNumberSieve() {

    // 1. 배열을 생성하여 초기화한다.
    for(int i=2;i<=number;i++) {
        a[i] = i;
    }

    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
    // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
    for(int i=2;i<=number;i++) {
        if(a[i]==0) continue; // 이미 지워진 수라면 건너뛰기

        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        for(int j=2*i;j<=number; j+=i) {
            a[j] = 0;
        }
    }

    // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
    for(int i=2;i<=number;i++) {
        if(a[i]!=0) printf("%d ", a[i]);
    }
}

int main(void) {
    primeNumberSieve();
    return 0;
}

reference: https://www.youtube.com/watch?v=5ypkoEgFdH8&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=24