[Algorithms] 에라토스테네스의 체 - 소수 판별하기

에라토스테네스의 체란?

💡

가장 대표적인 소수(Prime Number) 판별 알고리즘. 소수를 대량으로 빠르고 정확하게 구하는 방법이다.

 

 

소수 (Prime Number)

• 양의 약수를 두개만 가지는 자연수
• 1은 소수가 아니다
• ex) 2, 3, 5, 7, 11, ... 등의 자연수

 

---

 

에라토스테네스의 체를 왜 알아야 할까?

 

프로그래머스의 Lv.1 소수찾기 문제이다. 

1부터 숫자 N까지에 존재하는 소수의 개수를 구하고자 할 때, 일반적으로 아래와 같은 코드를 짜곤한다.

 

const answer = [];
for (let i=2; i<=N; i++) {
	let check = true
	for (let j=2; j<i; j++) {
    	if (i % j === 0) {
        	check = false;
        }
    }
    if (check) answer.push(i);
}

 

• N 이하의 모든 자연수를 하나씩 소수인지 판별하는 방법이다.
• 2부터 i보다 작은 모든 자연수 중 나누어 떨어지는 값이 있으면 소수가 아님으로 제외하고 소수인 자연수를 구할 수 있다.
• 하지만 시간복잡도가 O(N)으로 모든 경우의 수를 다 돌며 약수 여부를 확인하는 점에서 비효율적인 코드라고 볼 수 있다.

 

위와 같은 방법은 i의 제곱근까지만 for문을 돌려서 시간을 아주 조금 절약할 수는 있다.

약수는 제곱근을 기준으로 대칭을 이루기 때문에 O(N^(1/2)) 방식으로 검증하는 것이다.

 

그러나 이 마저도 문제처럼 1000000 이하의 자연수를 모두 판별하기엔 최적화된 코드라고 보긴 어렵다.

 

 

---

에라토스테네스의 체

• 소수를 판별하고 싶은 범위의 모든 자연수를 나열한다.
• 가장 작은 수부터 시작해 자기 자신을 뺀 해당 수의 배수를 모두 지운다.
• 만약 수가 이미 지워졌다면 건너 뛴다.
• 남아 있는 수를 모두 출력한다.

 

배수라 함은 당연히 자기 자신과 1을 제외한 또 다른 수가 약수로 존재하는 수임으로 이 원리를 이용한 코드를 짜볼 수 있다.

 

 

// 1. 소수를 판별하고 싶은 범위의 모든 자연수를 나열한다.
const arr = new Array(N+1).fill(0).map((v,i) => i); // [0,1,2,3,...,N]

// 2. 가장 작은 수부터 시작해 자기 자신을 뺀 해당 수의 배수를 모두 지운다.
for (let i = 2; i <= N; i++) {
	// 3. 만약 수가 이미 지워졌다면 건너 뛴다.
	if ( arr[i] !== 0 ) {
        for (let j = i+i; j <= N; j+=i) {
    		arr[j] = 0;
        }
    }
}

// 4. 남아 있는 수를 모두 출력한다.
arr.filter(v => v !== 0) // [1,2,3,5,...]
return arr.filter(v => v !== 0).length - 1

 

* 1은 소수가 아님으로 1을 빼줘야 한다.