[Algorithm/C++] 에라토스테네스의 체 - 특정 범위 수 소수 판별

 

 

1. 설명

에라토스테네스의 체는 소수를 찾는 방법 중 하나로서 수학자인 에라토스테네스가 발견하여 에라토스테네스의 체라고 한다.

 

 

에라토스테네스의 체는 소수를 판별해야 하는 상황 중 "2부터 N까지 수 중 소수 찾기"와 같이 특정 범위 수 중에서 소수를 찾는 데 사용할 수 있는 효율적인 방법이다.

 

출처: 위키백과 (에라토스테네스의 체)

 

원리를 요약하여 설명하자면

 

1. N+1의 크기를 갖는 bool 값을 저장할 배열 혹은 vector를 생성하고 True로 초기화한다.

 

크기를 N+1로 해주는 이유는 index로 보았을 경우 0부터 시작하여 N-1까지이기 때문에 N 위치의 저장하기 위하여 N+1 크기로 생성하는 것이다.

 

---

 

2. i=2부터 반복문을 시작하며 2의 배수들은 곧 2를 약수로 갖는다는 의미로서 소수가 아니다. 따라서 2의 배수 index 값들을 소수가 아니기 때문에 False로 변경해준다.

 

마찬가지로 i=3의 배수들, i=4는 이미 2의 배수로서 소수가 아닌 것으로 판별되었기 때문에 넘어가고, i=5의 배수들을 False로 변경해주는 과정을 반복해주면 소수가 아닌 수(Index)들은 False 값을 갖게 된다.

 

또한, 이러한 과정은 N까지 범위의 수들만 판별을 하면 되므로 i * i가 N이하가 되는 만큼만 반복문을 수행하면 된다.

 

---

 

3. 이제 2부터 N까지 True 값을 갖는 경우 해당 수가 소수인 것을 알 수 있게 된다.

 

 

 

2. 코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    // 1. 13까지 수 중 소수 찾기
    int num = 13;
    vector<bool> v(num + 1, true);

    // 2. 소수 판별
    for (int i = 2; i * i <= num; i++) {
        if (v[i]) {
            for (int k = i * i; k <= num; k += i) {
                v[k] = false;
            }
        }
    }

    // 3. 소수 확인
    cout << "소수 : ";
    for (int i = 2; i < v.size(); i++) {
        if(v[i]) cout << i << " ";
    }
    cout << "\n";

    return 0;
}

 

결과

 

위의 서 설명하였던 과정을 그대로 구현한 코드로서 각 과정을 살펴보면

 

 

1. Vector를 생성해주며 num(=13)까지의 수 중 소수를 판별하기 위하여 num+1 크기를 갖는 vector를 True로 초기화해주었다.

 

---

 

2. 반복문을 i=2부터 수행해주며 i*i가 num 이하가 될 때까지만 반복하여 실행해 준다.

 

v[i] = True일 경우 i는 소수이며 그 배수들은 소수가 아니라는 의미이므로 그 배수들의 값들을 반복문을 사용하여서 False 값으로 변경해 준다.

 

---

 

3. 위 과정이 끝나면 소수가 아닌 수들은 False로 변경되었으므로 True인 값만을 탐색하면 num(=13)까지의 범위에서 소수인 수를 판별해 낼 수 있다.

 

 

 

 

 

단, 에라토스테네스의 체는 특정 범위에서 소수인 수들을 판별해내는데 효율적으로 동작하지만 특정 수가 소수인지 판별하기 위해서 사용하기 위해서는 비효율적이다.

 

특정 수가 소수인지 판별하기 위한 방법은 아래 글을 참고하면 될 것 같다.

 

C++ 소수 판별하기