JavaScript로 배열에 포함된 모든 소수의 합 구하기

이번 글에서는 숫자 배열을 입력받아 배열 안에 있는 모든 소수(Prime Number)의 합을 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 다음과 같은 배열이 있다고 가정해 봅시다.

const arr = [43, 6, 6, 5, 54, 81, 71, 56, 8, 877, 4, 4];

이 배열에서 소수는 43, 5, 71, 877이며, 함수는 이 값들의 합을 반환해야 합니다.

43 + 5 + 71 + 877 = 996

소수 판별 로직 이해하기

소수란 1보다 크고, 1과 자기 자신 외에는 약수를 가지지 않는 수입니다. 따라서 소수 판별 함수는 다음 규칙을 따릅니다.

• 1은 소수가 아니므로 false를 반환합니다.
• 2는 유일한 짝수 소수이므로 true를 반환합니다.
• 그 외의 수는 2부터 n-1까지 나누어 떨어지는 값이 있는지 확인하고, 하나라도 있으면 소수가 아닙니다.

예제 코드

아래는 위 로직을 구현한 전체 코드입니다.

const arr = [43, 6, 6, 5, 54, 81, 71, 56, 8, 877, 4, 4];

// 소수 판별 함수
const isPrime = n => {
    if (n === 1) {
        return false;
    } else if (n === 2) {
        return true;
    } else {
        for (let x = 2; x < n; x++) {
            if (n % x === 0) {
                return false;
            }
        }
        return true;
    }
};

// 배열 내 소수의 합을 구하는 함수
const primeSum = arr => {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        if (!isPrime(arr[i])) {
            continue;
        }
        sum += arr[i];
    }
    return sum;
};

console.log(primeSum(arr));

코드 설명

isPrime 함수는 전달받은 숫자가 소수인지 여부를 판별합니다. 반복문을 통해 2부터 해당 숫자 직전까지의 값으로 나누어 보고, 나누어 떨어지는 경우 즉시 false를 반환하여 불필요한 연산을 줄입니다.

primeSum 함수는 배열을 순회하면서 각 요소가 소수인지 검사하고, 소수인 경우에만 합계에 더합니다. 소수가 아니면 continue 문으로 건너뜁니다.

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

996

성능 개선 팁

현재 코드는 시간 복잡도가 O(n²)에 가까워 큰 숫자가 많으면 느려질 수 있습니다. 제곱근까지만 검사하도록 조건을 x <= Math.sqrt(n)으로 바꾸면 판별 속도를 크게 향상시킬 수 있습니다.