🌠 문제
약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.
🌠 제한사항
- 1 ≤ n ≤ 100
🌠 입출력 예
n result
10 5
15 8
🌠 입출력 예 설명
입출력 예 #1
- 10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.
입출력 예 #2
- 15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.
🧞 풀이
function solution(n) {
// 합성수를 찾는다는 것은 곧 소수를 찾아서 제외하는 것이라 봐도 된다.
// 소수를 찾으려면? 다양한 방법이 있지만 에라토스테네스의 체를 써보자.
// 길이가 n인 배열 선언
let arr = new Array(n).fill(0);
// 2부터 시작하여 특정 수의 배수에 해당하는 수를 모두 지운다.
for (let i = 2; i <= n; i++) {
// 이미 지워진 수라면 건너뛴다.
if(arr[i]==-1) continue;
// 배수부터 출발하여, 가능한 모든 숫자를 지운다.
for (let j = 2*i; j<=n; j+=i) {
arr[j] = -1;
}
}
// 합성수의 갯수는 -1을 값으로 가지는 원소의 갯수랑 동일하다.
return arr.filter(e => e == -1).length;
}
'🧩 Algorithm > 🟧 JavaScript' 카테고리의 다른 글
[프로그래머스] 팩토리얼 (0) | 2023.04.10 |
---|---|
[프로그래머스] 최댓값 만들기 (1) (0) | 2023.04.10 |
[프로그래머스] 주사위의 개수 (0) | 2023.04.10 |
[프로그래머스] 배열 회전시키기 (0) | 2023.04.06 |
[프로그래머스] 공 던지기 (0) | 2023.04.06 |