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

문제 설명

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

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

 

제한 사항

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

 

입출력 예

numbers	result
10	4
5	3

 

첫번째 시도한 풀이

function isPrime(x){
    for(let i=2; i<=Math.sqrt(x); i++){
        if(x%i===0) return false;
    }
    return true;
}

function solution(n) {
    var answer = 0;
    
    for(let i=2; i<=n; i++){
        if(isPrime(i))
            answer++;
    }
    return answer;
}

 

 

2부터 소수이므로, 숫자 2부터 n까지 순회하면서, 각 숫자에 대해 isPrime(소수 인지 판별하는 함수)를 호출해서, 소수일 경우 answer의 값을 증가시켜서 총 소수의 갯수를 계산한다. isPrime은 2부터 Math.sqrt(x)까지의 숫자로 나누고, 나누어떨어지면 소수가 아니라고 판단하였다.

 

 

 

테스트케이스는 다 통과했는데, 시간복잡도에서 걸렸다....

따라서 시간복잡도 측면에서 더 나은 방법인 에라토스테네스의 체를 써보기로 했다. 

 

성공한 풀이

function solution(n){
    let array = Array(n+1).fill(true);
    array[0]=array[1]=false;
    
    for(let i=2; i<=Math.sqrt(n); i++){
        if(array[i]){
            for(let j=i*i; j<=n; j+=i){
                array[j]=false;
            }
        }
    }
    
    let answer = 0;
    for(let i= 2; i<= n; i++){
        if(array[i])answer++;
    }
    return answer;
}

 

일단 인덱스가 0부터 n까지인 배열을 선언하고, 0과 1은 소수가 아니기에 false로 초기화를 시켜주었다. 2부터 √n까지 반복하면서, true로 남아있는 숫자는 소수로 간주한다. 또한 i의 배수들도 모두 소수가 아니므로 false로 표시한다. 최종적으로 array[i]가 true인 값의 갯수를 세어서 반환한다. 

 

벌써 시간복잡도를 생각해야 될 때가 왔다니...벌써부터 어렵다 🥹