JavaScript로 특정 간격을 가진 두 소수 쌍 찾기

알고리즘 문제를 풀다 보면 소수(Prime Number)와 관련된 다양한 요구사항을 만나게 됩니다. 이번 글에서는 JavaScript를 활용해 주어진 범위 안에서 서로 일정한 간격(gap)만큼 떨어져 있는 두 소수 쌍을 찾는 방법을 단계별로 살펴보겠습니다.

문제 정의

첫 번째 인수로 숫자 gap을, 두 번째 인수로 두 개의 숫자로 구성된 범위 배열을 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 지정된 범위 내에 존재하면서 절댓값 기준으로 그 차이가 gap과 같은 소수 쌍을 배열 형태로 반환해야 합니다.

예시 조건

gap: 4
범위: [20, 200]
기대 결과: 20 이상 200 미만의 소수 중 차이가 4인 첫 번째 소수 쌍

접근 방법

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

소수 판별: 주어진 수가 소수인지 확인하는 헬퍼 함수를 작성합니다.
범위 내 소수 수집: 왼쪽 경계부터 오른쪽 경계까지 반복하면서 모든 소수를 배열에 저장합니다.
간격 비교: 인접한 소수들의 차이를 순서대로 검사하여 gap과 일치하는 첫 번째 쌍을 반환합니다.

구현 코드

다음은 위 접근 방식을 구현한 전체 코드입니다.

const gap = 4;
const range = [20, 200];
const primesInRange = (gap, [left, right]) => {
    const isPrime = num => {
        for(let i = 2; i < num; i++){
            if(num % i === 0){
                return false;
            };
        };
        return true;
    };
    const primes = [];
    const res = [];
    for(let i = left; i < right; i++){
        if(isPrime(i)){
            primes.push(i);
        };
    };  
    let currentNum = primes[0];
    for(let j = 1; j < primes.length; j++){
        if(primes[j] - currentNum === gap){
            res.push(currentNum, primes[j]);
            return res;
        }else{
            currentNum = primes[j];
        };
    };
    return null;
};
console.log(primesInRange(gap, range));

코드 설명

코드의 핵심 로직을 부분별로 자세히 살펴보겠습니다.

1. 소수 판별 함수 (isPrime)

isPrime 함수는 2부터 num-1까지의 모든 수로 나누어 떨어지는지 검사합니다. 하나라도 나누어 떨어지면 소수가 아니므로 false를 반환하고, 끝까지 통과하면 true를 반환합니다.

2. 범위 내 소수 수집

left부터 right-1까지 반복하면서 isPrime 검사를 통과한 숫자들만 골라내어 primes 배열에 저장합니다.

3. 간격 비교 및 결과 반환

primes 배열을 순회하면서 현재 소수와 다음 소수의 차이가 gap과 정확히 일치하는지 확인합니다. 조건을 만족하는 쌍을 발견하면 즉시 해당 두 소수를 담은 배열을 반환하고, 끝까지 찾지 못하면 null을 반환합니다.

실행 결과

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

[37, 41]

20 이상 200 미만 범위에서 차이가 4인 첫 번째 소수 쌍은 바로 37과 41입니다. 실제로 37과 41 사이에는 다른 소수가 존재하지 않으며, 두 수의 차이는 정확히 4입니다.

성능 개선 팁

현재 isPrime 함수는 O(n)의 시간 복잡도를 가지므로 범위가 커지면 속도가 느려질 수 있습니다. 제곱근까지만 검사하도록 수정하면 성능을 크게 향상시킬 수 있습니다.

const isPrime = num => {
    if(num < 2) return false;
    for(let i = 2; i * i <= num; i++){
        if(num % i === 0){
            return false;
        }
    }
    return true;
};

또한 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하면 넓은 범위의 소수를 한 번에 더욱 효율적으로 구할 수 있으므로, 대량의 데이터를 처리할 때 유용한 대안이 됩니다.

JavaScript로 특정 간격을 가진 두 소수 쌍 찾기 – 단계별 구현 가이드