[프로그래머스/Javascript] 47. 소수 찾기

문제설명

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

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

---

제한조건

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

---

입출력예시

n	result
10	4
5	3

---

처음 풀이

function solution(n) {
    function prime(n){
    if(n < 2) return false  
    for(let i = 2; i <= Math.sqrt(n); i++){
        if(n % i === 0) return false
    }
    return true
}
    
    let count = 1
    for(let i = 2; i <= n; i++){
      if(prime(i)) count++
    }
    return count
}

처음 풀이는 효율성 테스트에 완전히 실패해버렸다. 나름 소수를 검증하는 과정에서 대상 숫자의 제곱근까지만 검증(약수는 작은 수와 큰 수가 연결되어 있어서)을 해서 효율성을 챙겼다고 생각했는데 부족한 모양이었다. 한참을 고민해도 떠오르는 것이 없어 '질문하기'에 다른 분이 올려주신 수학적인 지식이 담긴 힌트를 참고했다. 힌트는 다음과 같다.

• 1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있다.
• 어떤 자연수 n이 있을 때, √n 보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수이다.
• 2보다 큰 모든 짝수는 어차피 합성수이다.

위의 힌트들을 보고 내가 수정한 풀이는 이렇다.

---

수정된 풀이

function solution(n) {
    let arr = [2] // 2만 들어있는 소수 배열 생성
    
    function prime(n){
    if(n < 3) return false  // 2부터 돌아가게
    for(let item of arr){
        if(item > Math.sqrt(n)) break
        if(n % item === 0) return false
    }
    arr.push(n)
    return true
}
    
    let count = 1
    for(let i = 3; i <= n; i++){
        if(i % 2 !== 0){
            if(prime(i)) count++
        } 
    }
    return count
}

힌트를 통해 효율성을 높이기 위해서는 검증할 수의 제곱근까지만 검증하되, 소수로만 검증을 하면 된다는 것을 알게 되었다. 그래서 소수를 담을 배열 arr을 선언해 소수로 검증된 수를 배열에 담고 그 담긴 수들로만 돌아가면 검증하는 방식으로 바꾸었다. 또 2의 배수는 2를 제외하고 모두 소수가 아니기 때문에 아예 검증하지 않도록 하였다. 이렇게 실행했더니 효율성 테스트에서 통과할 수 있었다.

다른 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

이 풀이를 보고 감탄했다. 먼저 1에서부터 n까지 2의 배수를 제외한 값들과 거기서 1을 빼고 2를 더한 리스트를 만들어주고, 돌면서 소수를 구하면 소수의 배수들을 다 지워지는 방식으로 풀었다. 아마 예전에 지나가면서 봤던 에라토스테네스의 체를 이용한 것 같은데, 아주 깔끔하게 느껴지는 풀이였다.

---