JavaScript로 주어진 숫자보다 큰 가장 작은 소수 찾는 방법

이번 글에서는 양의 정수를 인수로 하나만 받아서, 그 숫자보다 바로 다음으로 큰 가장 작은 소수를 찾아 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제 정의

함수는 첫 번째이자 유일한 인수로 양의 정수를 받습니다. 그리고 이 값보다 큰 수들 중에서 가장 작은 소수를 찾아야 합니다.

예를 들어, 입력값이 다음과 같다면:

const num = 18;

18보다 큰 가장 작은 소수는 19이므로, 출력 결과는 아래와 같아야 합니다.

const output = 19;

풀이 접근 방식

해결 방법은 간단합니다. 입력받은 숫자보다 1 큰 값부터 시작하여 차례대로 수를 증가시키면서, 각 수가 소수인지 검사하면 됩니다. 소수 판별은 제곱근까지만 나누어 떨어지는지 확인하는 방식으로 효율적으로 처리할 수 있습니다.

예제 코드

다음은 위 로직을 구현한 전체 코드입니다.

const num = 18;

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

console.log(justGreaterPrime(num));

코드 설명

• 외부 루프: 입력값보다 1 큰 수(num + 1)부터 시작해 무한히 값을 증가시키며 후보를 탐색합니다.
• 내부 루프: 2부터 후보 수의 제곱근(d * d <= i)까지의 수로 나누어 떨어지는지 확인합니다. 나누어 떨어지면 소수가 아니므로 반복을 중단합니다.
• 소수 판별: 어떤 수로도 나누어 떨어지지 않으면 isPrime이 true로 유지되고, 해당 값을 즉시 반환합니다.

출력 결과

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

19

18보다 큰 가장 작은 소수인 19가 올바르게 반환된 것을 확인할 수 있습니다. 이 알고리즘은 제곱근까지만 검사하기 때문에 비교적 큰 수에 대해서도 효율적으로 동작합니다.