출처 : 프로그래머스
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
n | result |
---|---|
10 | 4 |
5 | 3 |
입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
function solution(n) {
let result = [];
for(let i=0; i<=n; i++){
result.push(i);
}
for(let i=2; i<Math.sqrt(n); i++){
if(!result[i]) continue;
for(let j=i+i; j<=n; j+=i){
result[j] = 0;
}
}
return result.filter(v => v !== 0).length-1;
}
Math.sqrt(number)
: number의 제곱근 리턴function solution(n) {
const s = new Set();
for(let i=1; i<=n; i+=2){
s.add(i);
}
s.delete(1);
s.add(2);
for(let j=3; j<Math.sqrt(n); j++){
if(s.has(j)){
for(let k=j*2; k<=n; k+=j){
s.delete(k);
}
}
}
return s.size;
}