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

https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스

 

---

[ 문제 ]

 

[ 내 풀이 ]

function solution(n) {
    let answer = 0;
    
    // 1부터 n까지 반복합니다.
    for(let i = 1; i <= n; i++){
    
        // 현재 숫자 i의 약수의 개수를 세기 위한 변수를 초기화합니다.
        let counter = 0;
        
        // 1부터 i까지 반복합니다.
        for(let j = 1; j <= i; j++) {
        
            // i가 j로 나누어 떨어지는지 확인합니다.
            if(i % j == 0) {
            
                // 나누어 떨어지면 약수의 개수를 증가시킵니다.
                counter += 1;
            }
        }
        
        // 약수의 개수가 2개 초과라면 (즉, 소수가 아니라면)
        if(counter > 2) {
        
            // 결과 값을 1 증가시킵니다.
            answer += 1;
        }
    }
    
    return answer;
}

 

[ 다른 풀이 ]

function solution(n) {

    // n+1 크기의 배열을 만들고 모든 요소를 1로 초기화합니다.
    let dp = new Array(n+1).fill(1);

    // 2부터 n까지 반복합니다.
    for(let i = 2; i <= n; i++){
    
        // dp[i]가 1인 경우 (소수인 경우)
        if(dp[i]){
        
            // i의 배수들을 0으로 설정합니다.
            for(let j = 2; i * j <= n; j++){
                dp[i * j] = 0;
            }
        }
    }

    // 배열 dp에서 값이 0인 요소들의 개수를 세어 반환합니다.
    return dp.filter(el => el === 0).length;
}

// 1. 크기가 n+1인 배열 dp를 만들고, 모든 요소를 1로 초기화합니다. 
//    이 배열은 각 숫자가 소수인지 여부를 나타냅니다. 
//    초기에는 모든 숫자를 소수로 가정합니다.

// 2. 2부터 n까지의 숫자 i에 대해 반복합니다.
//    만약 dp[i]가 1이라면, i는 소수입니다.
//    i가 소수라면, i의 배수들은 소수가 아니므로, 
//    i의 배수들을 0으로 설정합니다.

// 3. i의 배수들을 0으로 설정하기 위해, 
//    j를 2부터 시작하여 i * j가 n 이하인 동안 반복합니다.
//    dp[i * j]를 0으로 설정하여 i의 배수들을 소수가 아니라고 표시합니다.

// 4. dp 배열에서 값이 0인 요소들의 개수를 세어 반환합니다. 
//    이 값은 n 이하의 숫자 중 소수가 아닌 숫자의 개수를 나타냅니다.