[Programmers / JS] 12921번 - 소수 찾기

Problem

문제 보기

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

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

- 제한 조건
n은 2이상 1000000이하의 자연수입니다.

 

---

Solution

문제분석
return 1과 n 사이의 소수의 개수

문제풀이
에라토스테네스의 체를 이용하여 풀었다.
1. n까지의 새로운 배열 생성 (n+1을 하는 이유는 0부터 시작이기 때문)하여 true 대입
2. for문으로 n의 제곱근까지 확인하여 true일 경우 x의 배수 false (x만 남음)
3. 약수의 개수를 알아내야하므로 true인 것만 골라내고 0과 1은 빼야하므로 -2를 한다.

function solution(n) {
    const arr = new Array(n+1).fill(true);

    for(let i = 2; i <= Math.sqrt(n); i++){
        if(arr[i] === true){
            let j = 2;
            while (i * j <= n){
                arr[i * j] = false;
                j++;
            }
        }
    }
    
    return arr.filter(x => x === true).length - 2;
}