문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
n | result |
10 | 4 |
5 | 3 |
풀이 과정
// 에라토스테네스의 체 이론 적용
function solution(n) {
// n + 1 길이만큼 배열 생성 => [0, 1, 2, 3, ..., n]
// a[i] = i
let arr = Array(n + 1).fill().map((x, index) => index);
let result = 0;
// i는 2부터 확인해서 i의 배수들은 0으로 변경
for(let i = 2; i <= n; i++) {
if(arr[i] === 0) {
continue;
}
for(let j = i * 2; j <= n; j += i) {
arr[j] = 0
}
}
// 0이 아닌 놈들의 길이 -- 배열 생성할 때 0이 들어가서 1 빼줌
result = arr.filter(x => x !== 0).length - 1;
return result;
}
'알고리즘 > 프로그래머스 문제풀이' 카테고리의 다른 글
[프로그래머스 LEVEL2] 기능개발 / Javascript (0) | 2022.02.19 |
---|---|
[프로그래머스 LEVEL2] 거리두기 확인하기 / Javascript (0) | 2022.02.19 |
[프로그래머스 LEVEL1] 체육복 / Javascript (0) | 2022.02.19 |
[프로그래머스 LEVEL1] 행렬 테두리 회전하기 / Javascript (0) | 2022.02.19 |
[프로그래머스 LEVEL1] 신고 결과 받기 / Javascript (0) | 2022.02.19 |