[프로그래머스 Level 1] 소수찾기

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n                      result

10	4
5	3

 

---

위 문제를 처음 접했을 땐 평범한 소수찾기 문제인 거 같아서 매우 쉽다고 생각을 했다.

근데 범위 내에서 소수를 구하는 문제이기 때문에 에라토스테네스의 체를 활용하는 게 좋겠다는 생각이 들었다.

그럼 한 번 구현해보자.

function solution(n){
    var answer = Array(n+1).fill(1); // ㉠
    answer[1] = 0;
    answer[0] = 0;
    for(var j = 2; j <= Math.sqrt(n); j++){ // ㉡
        for(var k = j; j * k <= n; k++){ // ㉢
            answer[j * k] = 0;
        }
    }
    var count = 0;
    for(var num in answer) if(answer[num]) count++;
    return count;
}

위의 식에서 ㉠으로 인해 계속 효율성 문제가 발생했었다.

이전 식에선 answer이라는 배열에 n이 10이면 [0,,,,10] 이런 식으로 각 인덱스에 해당하는 값을 할당해주었다.

이러니 효율성에서 떨어질 수 밖에 없었다. 에라토스테네스의 체를 이용하는 경우, 인덱스를 통해 해당 수가 소수인지 아닌지를 판별하기 때문에 인덱스에 대응하는 값은 중요하지 않다. 고로 ㉠처럼 1로 채워주는 게 효율적이다.

 

㉡에서 Math.sqrt를 이용해주는 것도 효율성 측면에서 매우 중요하다. 

어떤 수 n이 있을 때, 이 수는 n이하의 소수의 곱으로 구성된다. 

즉, n은 약수로 Math.sqrt(n) 이하의 소수(n의 제곱근 이하의 소수)를 가질 것이다. ex) 49 = 7 * 7, 42 = 2 * 3 * 7

그렇기 때문에 ㉡처럼 n의 제곱근보다 작은 수의 범위에서 소수를 찾는 것만으로도 해결이 가능하다.

위와 마찬가지 이유로 ㉢에서 var k = j를 해줌으로써, 조금 더 효율적으로 해결할 수 있게 된다.