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

이 글에서는 숫자 하나를 인수로 받아, n보다 작은 모든 소수(prime number)의 합을 구해 반환하는 자바스크립트 함수를 작성하는 방법을 살펴보겠습니다.

문제 이해하기

예를 들어 n = 10이라면, 10 이하의 소수는 2, 3, 5, 7입니다. 이 네 수의 합은 17이므로, 함수는 17을 반환해야 합니다.

접근 방법

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

1단계 — 소수 판별: 어떤 수가 소수인지 확인하는 isPrime 함수를 만듭니다. 어떤 수가 소수가 아니라면 반드시 그 수의 제곱근(√num) 이하에 약수가 존재하므로, 제곱근까지만 검사하면 됩니다. 이렇게 하면 모든 수를 일일이 나눠 보는 것보다 훨씬 효율적입니다.

2단계 — 합계 계산: sumOfPrimes 함수가 num부터 2까지 역순으로 반복하면서 각 수가 소수인지 검사하고, 소수라면 합계 변수에 더합니다.

예제 코드

const isPrime = (num) => {
    let x = Math.floor(Math.sqrt(num));
    let j = x;
    while (j >= 2) {
        if (num % j === 0) {
            return false;
        }
        j--;
    }
    return true;
};
const sumOfPrimes = (num = 10) => {
    let iter = num;
    let sum = 0;
    while (iter >= 2) {
        if (isPrime(iter) === true) {
            sum += iter;
        }
        iter--;
    }
    return sum;
};
console.log(sumOfPrimes(14));
console.log(sumOfPrimes(10));

출력 결과

41
17

코드 동작 원리

sumOfPrimes(14)를 호출하면 14 이하의 소수인 2, 3, 5, 7, 11, 13을 모두 더해 41을 반환하고, sumOfPrimes(10)은 2 + 3 + 5 + 7 = 17을 반환합니다.

isPrime 함수 내부에서는 Math.sqrt(num)로 제곱근을 구한 뒤 Math.floor로 정수화하고, 해당 값부터 2까지 차례대로 나누어 떨어지는지 확인합니다. 중간에 한 번이라도 나누어 떨어지면 즉시 false를 반환하여 불필요한 연산을 줄여 실행 속도를 높입니다.