Algorithm - 에라토스테네스의 체 (효율성 좋게 소수 찾기)

소수는 자기자신만으로만 나눌 수 있는 값이다.

그래서 2부터 자기자신 숫자 전까지만 반복문으로 돌아서

나뉘어질 경우에 소수가 아님을 판별하는 로직으로 하니, 

효율성이 실패함. 에라토스테네스의 체를 사용하면 쉽게 해결 가능.

 

n까지의 소수를 알고 싶을때, n*1/2이하의 수의배수만 지우면 됨.

 

2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.

 -> 2를 제외한 2의 배수 지우고 ...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)로 가능