문제
풀이
소수 Prime Number를 찾는 문제입니다. 소수는 1과 자기 자신으로만 나눠지는 수 입니다. (단, 1은 소수가 아닙니다.)
위에 주어진 지식으로 소수를 구한다고 생각하면, 이론상으로는 숫자 n이 소수인지 알아보기 위해 2부터 n-1까지의 숫자를 반복하며, 나누어 떨어지는 숫자가 있는지 확인하고 만일 없다면, 소수라 할 수 있을 것입니다.
그런데 이렇게 계산하면 매번 n이 주어졌을 때, 2~n-1까지의 루프를 돌아야 하기 때문에 비효율적입니다.
효율적으로 소수를 구하는 공식이 따로 있는데, 바로 에라토스테네스의 체를 이용하여 소수를 구하는 것입니다.
위의 에라토스테네스의 체 공식을 쉽게 풀어서 말하면, 소수를 구하고자 하는 범위 2~n이 있을 때, 2~n의 제곱근에 해당하는 범위 안의 소수의 배수들을 계속 제외하면 결국 소수만 남는다는 것입니다.
이를테면 n=100일 때, 100까지의 소수를 구하고 싶다면, 100의 제곱근인 2~10까지의 숫자에 대한 소수의 배수만 제외하면 100까지의 소수를 구할 수 있는 것입니다.
100까지 숫자를 적어놓고, n의 제곱근(즉, 루트n) 보다 작은 소수인 2의 배수 제외, 3의 배수 제외, 5의 배수 제외 ... 이런식으로 제외해나가다보면 소수만 남게 됩니다.
여기서 또 "n의 제곱근까지의 소수는 또 어떻게 알까?" 하는 의문이 있는데 아래의 구현 코드를 잘 살펴보면 아실 수 있습니다. 아래 코드에서 잘 보면 i=2부터 진행하고 있고, j=i*i부터 진행합니다.
j=i*i부터 진행하며 매 루프마다 j가 j+=i로 증가한다는 것은, i에서 받은 첫 값(여기서는 2)을 소수로 인정 함과 동시에 i의 배수들은 전부 제외한다는 뜻입니다. 이렇게 제외하면 말 그대로 n범위까지의 소수의 배수를 전부 제외할 수 있습니다.
또한 위에서 소수의 배수로서 제외된 값은 소수가 아니므로, 배수를 제외하는 과정을 거칠 필요가 없습니다. 이를테면 4는 이미 소수인 2의 배수를 제외하는 과정에서 제외되었으므로 또 4의 배수를 제외할 필요는 없는 것입니다.
이렇게 i를 n의 제곱근까지 진행시키면 n까지의 모든 소수의 배수가 걸러지게 되며, 소수는 그대로 남게 됩니다.
여기서 filter함수를 이용하여, true인 것의 갯수를 세어주면 그게 바로 n까지의 소수의 갯수가 됩니다.
결국 에라토스테네스의 체란?
- 2~n까지의 수가 있다.
- 2부터 n의 제곱근(루트n)까지의 소수의 배수들을 제외시키면 소수만 남는다.
끝.
// 에라토스테네스의 체를 이용하여 2~n까지 소수 갯수 구하기
let solution = (n) => {
let arr = Array(n+1).fill(true).fill(false, 0, 2);
for(let i=2; i*i<=n; i++){
if(arr[i]){
for(let j=i*i; j<=n; j+=i){
arr[j] = false;
}
}
}
return arr.filter(e => e).length;
}