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

 

 

위 짤은 인터넷을 돌아다니다가 재밌어서 가져와봤습니다.

 

 

무튼 글을 시작하자면 알고리즘 문제를 풀다보면 소수 판별하라는 문제가 종종 보입니다.

해당 문제를 해결하기 위해선 소수 판별하는 알고리즘을 사용해야 합니다.

그래서 알고리즘 중에  '에라토스테네스의 체'가 가장 시간 복잡도도 우수하기 때문에 머릿속에 저장할 겸 정리해보려고 합니다.

 

 

목차

 

• 소수란
• 에라토스테네스의 체에 대해서
• 에라토스테네스의 체 구현(C++)

 

 

소수란

 

 

소수는 1과 자기 자신만을 약수를 갖는 1보다 큰 자연수입니다.

(참고로 1은 소수가 아닙니다.)

 

 

에라토스테네스의 체에 대해서

 

에라토스테네스의 체는 이름 그대로 무언가를 찾기 위해 체를 걸러내듯, 소수를 찾는 방법입니다.

 

알고리즘은

1. 2부터 찾고자하는 수까지 나열하고 1을 지웁니다.
2. 1 다음으로 큰 소수인 2를 제외하고 2의 배수를 모두 지웁니다.
3. 2 다음으로 큰 소수인 3을 제외하고 3의 배수를 모두 지웁니다. 
4. 3 다음으로 큰 소수인 5를 제외하고 5의 배수를 모두 지웁니다.
5. 5 다음으로 큰 소수인 7을 제외하고 7의 배수를 모두 지웁니다.
6. 위 과정을 반복하면 2에서 구하는 구간까지의 모든 소수가 남습니다.

 

 

위키백과

 

 

에라토스테네스의 체 구현(C++)

 

 

#include <iostream>

using namespace std;

bool ischecked[1001]; // false : 소수 X, true 소수

void printPrime(int num) {
    cout << "소수를 출력합니다." << '\n';
    for (int i = 2; i <= num; ++i) {
        if (ischecked[i])
            cout << i << ' ';
    }
}

void checkPrime(int num) {
    // 1을 지웁니다.
    ischecked[1] = false;

    // 2 부터 구하고자 하는 수 까지 범위를 잡습니다.
    for (int i = 2; i <= num; ++i) {
        if (!ischecked[i]) continue; // 지운 값 패스
        for (int j = i * i; j <= num; j += i) {
            // 배수들을 지웁니다.
            ischecked[j] = false;
        }
    }
}

int main(void) {
    // 1 에서 1000까지의 수를 소수라 가정합니다.
    fill(ischecked, ischecked + 1001, true);
    int num = 1000;
    checkPrime(num);
    printPrime(num);
    return 0;
}