[프로그래머스] 합성수 찾기

🌠 문제

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 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;
}