[JavaScript] 소수 찾기 Lv1

소수 찾기

문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.

출처: Programmers
소수 찾기

문제의 이해

무려 +7점을 받았다. 아마도 효율성테스트까지 있는 문제여서 그런가보다. 이 문제는 간단하지만 풀기 위해서는 아마 천재가 아니라면 “에라토스테네스의 체” 를 꼭 알고 있어야 하지 않나 싶다. 만약 모른다면 무지막지한 반복을 해야해서 효율성테스트를 통과하기가 쉽지 않아 보인다. 이 전의 문제가 소수 만들기라는 문제였어서 거기서 사용한, 주어진 n까지의 소수를 찾는 코드를 가져와서 살짝 수정하고 사용했다. 예전에 나였다면 방금 전에 만든 코드지만 그래도 공부하는 겸 다시 코드를 쳤을텐데 이제는 그냥 복붙하고 그 내용을 한번 더 이해하는 방식으로 시도했다.

내가 생각한 풀이 방법

1. 주어진 n 크기의 배열을 만들고 1로 초기화 한다.
2. 배열의 0번째는 0으로 초기화 한다. 이유는 1은 소수가 아니기 때문이다.(이후 3번부터 배열의 index시작은 0이고 소수는 1부터니까 참고해서 계산한다.)
3. 주어진 n의 제곱근 까지 반복문을 돌아서 에라토스테네스의 체 방식으로 소수가 아닌 수들의 값을 0으로 만든다.
4. 배열을 순회해서 1의 값을 가진 배열의 수를 세고(1값을 가진 배열들은 소수) 출력한다.

풀이

첫 번째 풀이

이미 한번 작성했던 코드라서 다시 한번 코드를 봤고, 여기서 전에 코드에서 문제지만 발견하지 못했던 for(let i = 2; i <= parseInt(Math.sqrt(n)); i++) 이 부분의 코드를 수정했다. 원래는 < 였는데 오류가 나서 확인해보니 조건은 <= 여야 한다. 이유는 작성한 post 소수 만들기에 적어두었다.

function solution(n) {
    var answer = 0;
    var primeNumberArr = [n];
    
    //주어진 n개의 배열을 1로 초기화
    for(let i = 0; i < n; i++){ 
        primeNumberArr[i] = 1;
    }
    
    //1은 소수가 아니므로 0으로 만들어주고 시작
    primeNumberArr[0] = 0;
    
    //n까지 1로 채운 배열에서 값 1은 소수고 0은 소수가 아니게 만들기 위한 반복문
    for(let i = 2; i <= parseInt(Math.sqrt(n)); i++){
        var j = 2;

        //현재 주어진 숫자가 이미 소수가 아니라고 판명됐으면 continue
        //이걸 하는 이유는 필요없는 반복을 할 필요가 없기 때문이다.
        //예를 들어서 i=4 이때 아래 제어문 체크를 안해주면 4도 반복하면서 4의 배수를 모두 제거하려고 한다.
        //10정도일때는 반복문이 도는 것이 동일하지만 100정도만 되어도 대략 50%이상 차이가 난다.
        if(primeNumberArr[i - 1] == 0){ 
            continue;
        }
        
        //n까지 반복해서 소수의 배수들을 제거하는 부분
        while(true){
            if(i * j > n){  //소수의 배수가 n보다 커지면 에라토스테네스의 체를 멈춤
                break;
            }
            primeNumberArr[(i * j) - 1] = 0;
            j++;
        } 
    }
    
    //주어진 n까지 소수가 몇개인지 구한다.
    for(let i = 0; i < n; i++){
        if(primeNumberArr[i] == 1){
            answer++;
        }
    }
    
    return answer;
}