에라토스테네스의 체

에라토스테네스의 체는 소수(Prime Number) 를 찾는 방법이다.

대량의 소수들을 구해야할 때 아주 유용한 알고리즘으로 O(N^1/2)의 시간복잡도를 갖는다.

[ 원리 ]

소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다.
에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘이다.
임의의 수 n 까지의 소수를 구하고자 할 때 2부터 √N (제곱근) 까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.

 

예를 들면  N=150 까지의 수 중 소수를 구한다고 해보자.

2부터 150까지 배열에 모두 넣은 후  소수가 아닌 것들을 모두 true로 체크하고

 

마지막에 체크가 안된 수들이 우리가 찾는 소수이다.

 

---

[ 구현 ]

우선 N 까지의 소수를 구하고자 하면, n 크기의 배열을 만든다.

int arr[151] // 150 까지의 소수를 구하고자 할 때

1. 2는 소수이므로 그대로 두고, N 까지의 2의 배수들을 false로 치환한다.
  ex) 4 , 6 , 8 , ...
2. 3은 소수 이므로 그대로 두고, N 까지의 3의 배수들을 false로 치환한다.
3. 4는 2의 배수임으로 1번 과정에서 false으로 치환 됐으므로 넘긴다.
4. 위의 과정을 N의 제곱근 까지 반복한다.

 

※ N의 제곱근 까지 반복하는 이유?

어떤 수 n이 1과 자신이 아닌 두 수의 곱으로 되어 있다고 생각해봅시다. (즉, 소수가 아님)

n = a*b 이고 n' 은 n 의 제곱근이라고 표현합시다.

여기서 만약,

a >= n' 이면, a*b = n = n'*n' 이므로 b<=n' 가 됩니다.

따라서 n' 까지만 검사를 하면 합성수를 이루는 a, b 중 작은 수(위에서는 b)까지는 충분히 체크할 수 있고,

합성수가 존재하지 않으면 소수라고 할 수 있습니다.

---

[ 코드 ]

vector<bool> arr(n+1);

arr[1] = true; // 1은 소수가 아니므로 true

for(int i = 2; i <= sqrt(n); i++){
    if(arr[i]) continue; // 이미 체크 됐으면 continue;
    for(int j = i + i; j <= n; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
        arr[j] = true;
}

// 소수 출력
for(int i = 2; i <= n; i++)
	if(!arr[i]) cout<< i << endl;

---

 

관련 알고리즘 문제 .

 

백준 수학은 너무 쉬워 - 2904번 https://www.acmicpc.net/problem/2904