합성수 찾기

1. 소인수분해 방법으로 찾기 : 시간복잡도 - O(n2)

소수 : 1과 자기 자신만을 약수로 가지는 수
약수 : 어떤 수를 나누어 떨어지게 하는 수 (나머지가 0인 수)

즉, 소수는 1과 자기 자신만을 나눌때만 나머지가 0이 되는 수이며
합성수는 1과 자기 자신만이 아닌 그 사잇수로도 나머지가 0이 되는 수로, 약수가 여러개인 수이다.

function solution(n) {
    let compositeNumbers = [];
   for(let i = 2; i <=n; i++) {
       for(let j = 2; j < i; j++ ) {
           if(i % j === 0) {
    // 1과 i 자기 자신을 제외한 나머지수를 i로 나눌때도 나누어 떨어지면 합성수이다
               compositeNumbers.push(i)
               break;
           }
       }
   }
    
    return compositeNumbers.length;
}

2. 에라토스테네스의 체를 이용하여 찾기 : 시간복잡도 - O(nlogn)

// 에라토스테네스의 체

function solution(n) {
    const filledArray = new Array(n+1).fill(1)
    //  0 1 2 3 4 5 6 7 8 9 10 -> index
    // [1,1,1,1,1,1,1,1,1,1,1] => 시작
    // [1,1,1,1,0,1,0,1,0,1,0] => i는 2일 때
    // [1,1,1,1,0,1,0,1,0,0,0] => i는 3일 때
    // ...
    
    for(let i=2; i<= n; i++) {
        if(filledArray[i]) {
            for(let j=2; i*j <=n; j++) {
                if(filledArray[i*j]) {
                filledArray[i*j] = 0;             
                }
            }
        }
    }
    return filledArray.filter(num => num === 0).length
}