[프로그래머스 Lv.1] 소수 찾기 javascript

function solution(n) {
    var answer = 0;

    // 1에서 n까지의 숫자를 담은 배열 생성
    const numbers = Array.from({ length: n }, (_, i) => i + 1);

    // 각 숫자의 약수 개수를 구함
    numbers.forEach(num => {
        let divisorCount = 0;

        // 1부터 num까지 나누어떨어지는지 확인
        for (let i = 1; i <= num; i++) {
            if (num % i === 0) {
                divisorCount++;
            }
        }

        // 약수의 개수가 2개이면 소수
        if (divisorCount === 2) {
            answer++;
        }
    });

    return answer;
}

 

처음 풀이었는데 테스트 후반 부에 시간 초과로 실패가 떴다.

아래는 에라토스테네스의 체를 사용하는 것이라고 한다.

function solution(n) {
    var answer = 0;

    // 1부터 n까지 true로 초기화된 배열 생성
    const isPrime = Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

    // 에라토스테네스의 체로 소수 판별
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false; // i의 배수는 소수가 아님
            }
        }
    }

    // 소수 개수 세기
    answer = isPrime.filter(value => value).length;

    return answer;
}

 

최적화된 이유:

1. 배수 제거 최적화:
   • iii의 배수 중 i2i^2i2보다 작은 값은 이미 처리되었으므로 i2i^2i2부터 시작합니다.
   • j+=ij += ij+=i: iii의 배수를 한 번에 처리해 불필요한 연산을 줄입니다.
2. 불필요한 반복 제거:
   • n\sqrt{n}n​까지만 반복합니다. nnn보다 큰 배수의 여부는 이미 작은 소수들로 판별되기 때문입니다.
3. 배열로 상태 관리:
   • 소수 여부를 배열로 관리하여 숫자 하나하나를 직접 계산하지 않아도 됩니다.

...눈물 난다