JavaScript로 특정 범위 내 소수 개수 구하기

문제 소개

이번 글에서는 두 개의 숫자, 예를 들어 a와 b를 입력받아 두 수 사이(경계값 포함)에 존재하는 소수의 총 개수를 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 다음과 같습니다.

a = 2, b = 21일 때,
두 수 사이의 소수는 2, 3, 5, 7, 11, 13, 17, 19입니다.

소수의 개수는 총 8개이므로, 우리가 만들 함수는 8을 반환해야 합니다.

접근 방법

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

소수 판별: 주어진 숫자가 소수인지 확인하는 함수(isPrime)를 만듭니다.
범위 순회: a부터 b까지의 모든 숫자를 순회하면서 소수인 경우만 카운트하는 함수(primeBetween)를 만듭니다.

1. 소수 판별 함수 (isPrime)

isPrime 함수는 2부터 num / 2 + 1까지의 수로 차례대로 나누어 보고, 하나라도 나누어 떨어지면 약수가 존재한다는 의미이므로 false를 반환합니다. 끝까지 검사해도 나누어 떨어지는 수가 없다면 소수이므로 true를 반환합니다.

2. 범위 내 소수 개수 세기 (primeBetween)

primeBetween 함수는 Math.min()과 Math.max()를 활용해 두 인자 중 작은 값부터 큰 값까지 순회합니다. 덕분에 인자의 전달 순서와 상관없이 항상 올바른 결과를 얻을 수 있습니다. 각 숫자가 isPrime을 통과할 때마다 카운트를 증가시키고, 최종적으로 그 값을 반환합니다.

예제 코드

const isPrime = num => {
    let count = 2;
    while(count < (num / 2)+1){
        if(num % count !== 0){
            count++;
            continue;
        };
        return false;
    };
    return true;
};
const primeBetween = (a, b) => {
    let count = 0;
    for(let i = Math.min(a, b); i <= Math.max(a, b); i++){
        if(isPrime(i)){
            count++;
        };
    };
    return count;
};
console.log(primeBetween(2, 21));

실행 결과

콘솔에는 다음과 같은 출력이 나타납니다.

효율성 개선 팁

현재 구현은 num / 2까지만 검사하므로 모든 수로 나누는 방식보다는 빠르지만, 더 최적화할 여지가 있습니다.

제곱근까지만 검사: 약수는 항상 쌍으로 존재하므로, count * count <= num 조건으로 제곱근까지만 확인해도 충분합니다. 검사 횟수가 크게 줄어들어 성능이 향상됩니다.
짝수 처리: 2를 제외한 모든 짝수는 소수가 아니므로, 2를 먼저 처리한 후 홀수만 검사하면 연산량을 절반으로 줄일 수 있습니다.
경계값 처리: 1 이하의 숫자는 소수가 아니므로, isPrime 함수 초입에 if (num < 2) return false;를 추가하면 더 견고한 코드가 됩니다.

마무리

이처럼 소수 판별 로직과 범위 순회 로직을 분리하면 코드의 가독성과 재사용성이 높아집니다. 필요에 따라 제곱근 검사나 에라토스테네스의 체 같은 알고리즘을 적용하면 훨씬 넓은 범위에서도 빠르게 소수를 계산할 수 있습니다.