[Algorithm] 에라토스테네스의 체

에라토스테네스의 체란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

 

소수란? 간단하게 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의할 수 있다. 

 

단일 숫자 소수 여부 확인

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간복잡도로 빠르게 구현할 수 있다. 

 

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나눌 수 있는 둘 중에 하나는 N 제곱근 이하이기 때문이다.

 

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

 

에라토스테네스의 체 원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법을 이용한다. 

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

 

에라토스테네스의 체 구현하기 (Javascript)

const solution = (n) => {
	let answer = 0;
    const prime = [];
    const arr = Array(n).fill(0);
    
    for(let i=2; i<=n; i++){
    	arr[i] = i;
    }
    
    for(let i=2; i<=n; i++){
    	if(arr[0] === 0) continue;
        prime.push(i);
        arr[i] = 0;
        
        for(let j=i; j<=n; j+=i){
        	if(arr[j] === 0) continue;
            arr[j] = 0;
        }
    }
    answer = prime.length;
    
    return anwser;
}//solution