[알고리즘] 에라토스테네스의 체

에라토스테네스의 체란?

에라토스테네스의 체는 가장 대표적인 *소수(Prime Number) 판별 알고리즘으로, 소수를 대량으로 빠르고 정확하게 구하는 방법입니다.

 

*소수 : 양의 약수를 두개(1과 자신)만 가지는 자연수

 

일반적으로 효율적인 소수 판별 알고리즘

const arr = [];

for(let i=2;i<=10;i++) {
    let find = true;
    for(let j=2;j<=Math.sqrt(i);j++) {
        if(i%j == 0) {
            find = false;
            break;
        }
    }
    if(find) {
        arr.push(i);
    }
}

console.log(arr); // [2, 3, 5, 7]

 

가장 생각하기 쉬운 N의 소수 판별 알고리즘은 2 ~ N-1까지의 숫자 중에서 나누어 떨어지는 수가 없을때 소수라고 판별 할 수 있지만, N의 약수는 무조건 √N범위 안에 존재하기 때문에 √N까지 확인했을 때 O(√N)으로 조금 효율적으로 소수를 구할 수 있습니다. 따라서 1개의 숫자에 대해 소수를 구할 때 주로 사용됩니다.

 

에라토스테체네스의 체 알고리즘

소수를 대량으로 빠르고 정확하게 구하기 위해서는 에라토스테체네스의 체 알고리즘을 사용하는 것이 가장 효율적입니다.

 

const arr = [];
const check = Array(10+1).fill(true);
let m = Math.floor(Math.sqrt(10));

//i = 2 부터 i의 배수를 모두 true로 지웁니다.
//이때, 이미 지워진 숫자는 continue합니다.
for(let i = 2; i <= m; i++){
    if(check[i]){
        arr.push(i);
        let temp = i+i;
        while(temp < check.length){
            check[temp] = false;
            temp += i;
        }
    }
}
for(let i = m+1; i < check.length; i++){
    if(check[i]) arr.push(i);
}

console.log(arr); // [2, 3, 5, 7]

 

에라토스테체네스의 체는 가장 먼저 소수를 반별할 범위만큼 배열을 할당하고 그 인덱스에 true값을 넣어줍니다.

다음으로, 2 ~ √N 까지 자신을 제외한 각 숫자의 배수들의 인덱스에 해당하는 배열값을 false로 제외시킵니다. 이때, 각 숫자의 배수들을 제외시키 전에 이미 false값이라면 해당 수의 배수들은 이미 제거됐으므로 건너뜁니다.

 

예를 들어, N이 10인 경우 Math.sqrt(10) = 3.1622776601683795 이므로 2, 3, 4의 배수들을 제외시킵니다.

 

1) 2의 배수를 제거 

 

true (i=2)

true

false

true

false

true

false

true

false (i=10)

 

2) 3의 배수를 제거

 

true

true

false

true

false

true

false

false

false

 

 

따라서, 배열에서 true인 index들만 뽑아낸다면 2, 3, 5, 7 이 되고 시간 복잡도는 O(N^(1/2))로 계산이 가능합니다.

 

 

[참고]

https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221233595886&redirect=Dlog&widgetTypeCall=true&directAccess=false 

22. 에라토스테네스의 체