코딩테스트/프로그래머스[Javascript/자바스크립트] 프로그래머스 Lv.1 - 소수 찾기

🍒 문제 설명

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

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

🍒 제한 사항

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

🍒 입출력 예

n	result
10	4
5	3

🍒 입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

🍒 작성 솔루션

function solution(n) {
    var answer = 0;
    const arr = new Array(n+1).fill(true);
    
    // 1은 소수가 아니기에 초기셋팅은 2부터, ++i인 이유는 2는 소수이다
    for (let i = 2; i <= n; ++i){
        // 2의 배수는 소수가 아니기 때문에 소수가 아닌것들은 false
        for (let k = i*2; k <= n; k += i) {
            arr[k] = false;
        }
    }
    // true 갯수가 곧 소수의 갯수. true 갯수 카운트하여 answer에 대입
    for (let i = 2; i <= n; ++i) {
        if(arr[i] === true){
            answer++;
        }
    }
    return answer;
}

🍒 끄적끄적

소수를 구하는 방법에는 '에라토스테네스의 체'를 많이 이용하는데 임의의 자연수에 대하여, 그 자연수 이하의 소수를 모두 찾아주는 방법이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다
2. 2는 소수이다
3. 자기 자신을 제외한 2의 배수는 소수가 아니다
4. 3은 소수이다
5. 자기 자신을 제외한 3의 배수는 소수가 아니다
6. 5는 소수이다
7. 자기 자신을 제외한 5의 배수는 소수가 아니다
8. 7은 소수이다
9. 자기 자신을 제외한 7의 배수는 모두 지운다
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다