PR - 소수 찾기

문제 및 예시

지난 풀이 참고

풀이

• 1 을 제외하고 2 부터 n까지의 수를 빈 배열 numbers 에 넣는다.
• n이 소수가 아니라면 1혹은 n 이 아닌 임의의 수 a와 b의 합성수이다.
• 그러므로 n 의 제곱근까지만 순회하는 루프를 만든다.
• numbers 배열에 존재하는 수num 의 제곱을 구한다.
• 루프를 돌면서 매번 num의 제곱에서 num을 더한 수 j를 구한다.
• numbers[j-1] 을 삭제한다.

풀이 해석

• 에라토스테네스의 체를 활용한 방법으로, 모든 수가 자신의 제곱에서부터 시작해 자신만큼 더한 숫자를 없애는 풀이이다.
• 이렇게 하면 2와 3을 검사할 때 대부분의 합성수가 지워지고, 지워지지 않은 수는 소수의 제곱에서부터 시작하는 소수의 배수이다. (예를들면 11의 제곱 121)
• 11을 검사할 때 자신의 제곱 121에서 시작해 121 + 11 을 지우고, 121 + 11 + 11 을 지우므로 n 미만의 모든 합성수를 지울 수 있다.

코드

function solution(n) {

    let answer = 0;
    let numbers = [];
    for(let i = 1; i <= n; i++) {
        numbers.push(i);
    }

    for(let i = 1; i*i < n; i++) { 
        if(numbers[i]) {                
            let num = numbers[i];       
            for(let j = num*num; j <= n; j += num) { 
                numbers[j-1] = 0;
            }
        }
    }
    numbers = numbers.filter((el) => {
        if(el) return el;
    })
    numbers.shift();
    answer = numbers.length;

    return answer;
}