에라토스테네스의 체

: 가장 대표적인 소수(Prime Number) 판별 알고리즘

소수를 대량으로 빠르고 정확하게 구하는 방법

⬇️ 가장 기본적인 소수 판별 함수

bool primeNumber(int num) {
    for(int i=2; i<num; i++) {
        if(x % i == 0) { return false; }
    }

    return true;
}

이와 같은 알고리즘의 시간 복잡도는 O(N)이다. (굉장히 비효율적)

사실 해당 수의 제곱근까지 약소 여부를 검증하면 시간 복잡도를 줄일 수 있다.
예를 들어, 8의 경우 2 4 = 4 2와 같이 대칭을 이루고 있기 때문이다.

⬇️ 이와 같은 경우 시간 복잡도는 O(N^(1/2))

bool primeNumber(int num) {
    if(num < 2) { return false; }

    for(int i=2; i<=sqrt(num); i++) {
        if(num % i == 0) { return false; }
    }

    return true;
}

하지만 이렇게 한 두개의 소수를 판별하는 것이 아닌, 대량의 소수를 한꺼번에 판별하고자 할 때 쓰는 것이 에라토스테네스의 체이다.

---

방법

1. 이는 가장 먼저 소수를 판별할 범위 만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다.

2. 그리고 2부터 시작해 그 수의 배수가 되는 숫자들을 모두 지워준다. (이때, 자기 자신은 지우지 않는다.)

(이미 지워진 숫자의 경우 건너뛴다.)

3. 그리고 2부터 시작해 남아있는 숫자들을 출력한다.
   
   ➡️ 2, 3, 7, 11, 13, 17, 19, 23

---

✔️ 코드

⬇️ 소수를 에러토스테네스의 체로 판별해 출력하는 코드

int number[100001];

void primeNumber(int num) {
    for(int i=2; i<=num; i++) {
        number[i] = i;
    }
    
    for(int i=2; i<=num; i++) {
        if(number[i] == 0) { continue; }
        
        for(int j=i+i; j<=num; j+=i) {  // 자기 자신을 제외하고 삭제
            number[j] = 0;
        }
    }

    for(int i=2; i<=num; i++) {
        if(number[i] != 0) { cout << number[i] << ' '; }
    }
}