JavaScript에서 지정된 숫자 이후의 첫 번째 소수 찾는 방법

문제 정의

하나의 숫자를 매개변수로 받아, 그 숫자보다 큰 첫 번째 소수(Prime Number)를 반환하는 JavaScript 함수를 작성해야 합니다.

예를 들어, 입력값이 24라면 24보다 큰 첫 번째 소수인 29를 출력해야 합니다.

해결 접근 방식

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

1단계 — 소수 판별 함수: 임의의 수 n이 소수인지 검사하는 isPrime 함수를 작성합니다. 1은 소수가 아니고, 2는 소수입니다. 그 외의 수는 2부터 n-1까지 차례대로 나누어 보았을 때 나머지가 0이 되는 값이 하나라도 있으면 소수가 아니라고 판정합니다.

2단계 — 다음 소수 탐색: nearestPrime 함수는 입력받은 숫자를 1씩 증가시키면서(isPrime(++num)) 소수가 발견될 때까지 반복한 뒤, 해당 값을 반환합니다.

구현 코드

const num = 24;
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 nearestPrime = num => {
    while(!isPrime(++num)){};
    return num;
};
console.log(nearestPrime(24));

실행 결과

콘솔에는 다음과 같이 출력됩니다.

29

코드 동작 원리

nearestPrime(24)가 호출되면 num은 25부터 시작하여 26, 27, 28 순으로 증가하며 소수 여부를 검사합니다. 25는 5로, 27은 3으로 나누어떨어지고, 28은 짝수이므로 세 수 모두 소수가 아닙니다. 마침내 29에 도달했을 때 2부터 28까지 어떤 수로도 나누어떨어지지 않으므로 소수로 판정되어 최종적으로 반환됩니다.

이처럼 소수 판별 로직과 단순 반복문만으로도 특정 숫자 이후의 가장 가까운 소수를 손쉽게 구할 수 있습니다. 참고로 성능을 더 높이고 싶다면, 제곱근까지만 나누어 검사하거나 에라토스테네스의 체를 활용하는 방법도 고려할 수 있습니다.