에라토스테네스의 체(소수 찾기) C++ / 과정 / 시간복잡도 :: DANIDANI

알고리즘 개념

• 고대 그리스 수학자 에라토스테네스가 만들어 낸 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
• 빠르고 정확하게 소수를 찾는 알고리즘
• n까지의 소수를 알고 싶을 때, n^1/2 이하의 수의 배수만 지우면 된다.

과정

1. 배열 생성 후 초기화한다. (1은 소수가 아니니 지우고 시작)
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
   1. 2를 제외한 2의 배수를 지운다.
   2. 3을 제외한 3이 배수를 지운다.
   3. 반복
3. 남아있는 수가 소수!

코드

vector<bool> arr(n+1);
arr[1] = true;
for(int i = 2; i <= sqrt(n); i++){
    if(arr[i]) continue;
    for(int j = i + i; j <= n; j += i)
        arr[j] = true;
}

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

시간 복잡도

제곱근까지만 약수의 여부를 검증하면 O(N^1/2)로 가능하다.