자바스크립트로 n 이하의 모든 소수 구하기

문제 개요

숫자 n을 입력받아, n 이하의 모든 소수를 담은 배열을 반환하는 자바스크립트 함수를 작성해야 한다고 가정해 보겠습니다.

예를 들어 n이 24라면, 24 이하의 소수 목록은 다음과 같습니다.

const output = [2, 3, 5, 7, 11, 13, 17, 19, 23];

접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

• 소수 판별: 특정 수가 소수인지 확인하는 함수를 만듭니다. 2부터 해당 수의 절반까지 차례대로 나누어 보고, 하나라도 나누어 떨어지는 수가 있으면 소수가 아닙니다.
• 범위 탐색: 2부터 n까지의 모든 수를 순회하면서, 소수로 판별된 값만 결과 배열에 추가합니다.

구현 코드

다음은 위 로직을 구현한 전체 코드입니다.

const num = 24;
const isPrime = num => {
    let count = 2;
    while(count < (num / 2)+1){
        if(num % count !== 0){
            count++;
            continue;
        };
        return false;
    };
    return true;
};
const primeUpto = num => {
    if(num < 2){
        return [];
    };
    const res = [2];
    for(let i = 3; i <= num; i++){
        if(!isPrime(i)){
            continue;
        };
        res.push(i);
    };
    return res;
};
console.log(primeUpto(num));

코드 설명

• isPrime(num): 2부터 num/2 + 1 미만까지의 수로 num을 나누어 떨어지는지 검사합니다. 중간에 약수가 발견되면 즉시 false를 반환하고, 끝까지 약수가 없으면 true(소수)를 반환합니다.
• primeUpto(num): n이 2보다 작으면 소수가 존재하지 않으므로 빈 배열을 반환합니다. 2는 유일한 짝수 소수이므로 결과 배열에 먼저 넣은 뒤, 3부터 n까지 isPrime으로 검사하여 통과한 수만 추가합니다.

성능을 더 개선하고 싶다면, 소수 판별 범위를 num의 제곱근(Math.sqrt(num))까지만 검사하도록 줄이면 불필요한 연산을 크게 줄일 수 있습니다.

실행 결과

코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.

[
    2,  3,  5,  7, 11,
    13, 17, 19, 23
]