다른사람 풀이:
function solution(n) {
let answer = 0;
const arr = new Array(n+1).fill(true); // 초깃값 설정
const end = Math.sqrt(n)
for(let i = 2; i <= end; ++i){
// 이미 소수가 아닌 인덱스는 건너뛴다.
if(arr[i] === false){
continue;
}
// 소수가 아닌 데이터는 false로 입력한다.
for(let k = i * i; k <= n; k += i){
arr[k] = false;
}
}
// 소수의 갯수를 구한다.
for(let i = 2; i <= n; ++i){
if(arr[i] === true){
answer++;
}
}
return answer;
}소수 문제를 봤을 때 배열 없이 더 빠른 방법이 없을까 고민하다가 못 찾고, 소수를 공부할 때 체를 걸러주듯 숫자의 배수들을 지워주는 방법이 떠올랐는데 뭔지 이름이 생각 안 나서 찾아보고 다시 문제를 풀었다. 수학자 에라토스테네스가 소수를 찾는 방법을 발견했는데 그것이 에라토스테네스의 체 였다. 방법은 이러하다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다.
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
- 자기 자신을 제외한 3의 배수를 모두 지운다.
...
위의 방법대로 배수를 모두 지우면 남아있는 수는 소수가 된다. 엄청나게 효율적인 방법이다.
테스트 결과 적확성과 효율성 모두 잘 통과했다. 그래도 이번에는 뭔가 머리를 좀 쓴 것 같은 문제였다.
라고 한다.