[프로그래머스 JavaScript] Level1 소수 찾기

 더 좋은 방법좀 알려주세요ㅠㅠ 

 

소수 찾기를 검색하면 나오는 에라토스테네스의 체의 방법을 사용해 보았다.

2 소수이면 2의 배수는 소수가 아니다.

3 소수이면 3의 배수는 소수가 아니다.

4는 2의 배수로 소수가 아니다.

n개까지 구한다고 했을 경우, n의 제곱근까지만 소수를 찾으면 된다.

 

function solution(n) {
    let answer = 0;
    let arr = [];
    
    // 초기배열 셋팅
    // 0과 1은 소수가 아니기 때문에 처음부터 0을 넣음
    for (let i = 0; i <= n; i++) {
        if (i == 1)
            arr[i] = 0;
        else
            arr[i] = i;       
    }
    
    // 소수 찾기
    for (let i = 2; i*i <= n ; i++) { // 제곱근까지 반복
        if (arr[i] != 0) { // 0아니면 소수
            for (let j = i+i; j <= n; j += i) { // 소수의 배수들은 소수가 아님
                arr[j] = 0; // 소수 아닌것을 0으로 표현
            }
        }
    }
    
    // 소수의 개수 구하기
    for (let i = 0; i <= n; i++) {
        if (arr[i] != 0) // 소수 아닌것을 0으로표현했으니, 0이아니면 소수
            answer++; // 소수의 갯수 카운트
    }
    
    return answer;
}