[알고리즘 || 프로그래머스] 🔁소수 찾기

 

오늘은 시간의 한계를 못넘어서 비난님의 코드를 보고 공부하는 시간으로 대체했다. 

처음엔 for 문으로 1, 2, 를 제외한 이후의 숫자부터 약수의 개수를 세어보고 소수인지 아닌지 판별하는 방식으로 풀었는데, 

범위가 너무 많았는지 시간초과로 통과되지 못했다.

 

이렇게 제곱근을 이용하면 훨씬 더 적은 범위 내에서 약수를 구할 수 있다. 

어차피 약수는 두 수의 곱으로 이뤄지기 때문에 16의 약수인 2를 구했다면 자동으로 8도 존재하는 것이기 때문이다.

 

 

비난님의 코드를 보면 소수를 구한다기 보단, 

소수가 아닌 수를 소거해주는 방식을 채택하고 있다.

function solution(n) {
    let isPrime = new Array(n + 1).fill(true).fill(false, 0, 2)
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false
            }
        }
    }
    return isPrime.filter(Boolean).length;
}

처음엔 잘 이해가 안갔지만, 

하나씩 보며 예제를 돌려보니 이해가 갔다.

 

먼저 isPrime 이란 배열을 만들어주는데, n 보다 하나 더한 길이로 만들어준다. 

이는 for 문에서 index 와 i 라는 약수를 일치시키기 위함이다. 

 

true 로 채운 배열에서 소수가 아닌 것들만 false 로 바꿔준다.

처음에 index 0, 1 는 소수가 아니기 때문에 false다.

 

그럼 처음엔 2가 true 이므로

안쪽에 있는 for 문을 돌며 2*2 부터 2의 배수들이 false 가 된다. (4, 6, 8, 10,,,) 

그 다음은 3*3 부터 3의 배수들이 false 가 된다. (9, 12, 15, 18, 21,,,)

이런식으로 다음은 5, 7, 등으로 소수가 아닌 숫자들이 소거된다. 

 

전부 소거된 배열에서 true 인 요소만 filter 로 걸러준 배열의 length 가 n 까지의 소수의 개수가 된다. 

 

소거법 므찌다!