JavaScript로 주어진 숫자 이후의 첫 번째 소수 찾기

이번 글에서는 숫자를 하나 입력받아, 그 수보다 큰 값 중에서 처음으로 등장하는 소수(prime number)를 반환하는 자바스크립트 함수를 작성해 보겠습니다.

문제 정의

예를 들어 입력값이 24라면, 24보다 큰 숫자 중 가장 먼저 만나게 되는 소수는 29입니다.

(25는 5×5로 나누어지고, 26과 28은 짝수, 27은 3×9이므로 모두 소수가 아니며, 29가 첫 번째 소수입니다.)

접근 방법

구현 로직은 매우 간단합니다.

입력된 숫자를 1씩 증가시키면서 확인합니다.
각 숫자가 소수인지 판별하는 헬퍼 함수 isPrime()을 사용합니다.
소수를 발견하면 즉시 그 값을 반환하고 종료합니다.

코드 예제

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;
    }
};

// num보다 큰 첫 번째 소수를 찾는 함수
const nearestPrime = num => {
    while (!isPrime(++num)) {};
    return num;
};

console.log(nearestPrime(24));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

코드 설명

1. isPrime() 함수

이 함수는 전달받은 숫자가 소수인지 여부를 판별합니다.

1은 소수가 아니므로 false를 반환합니다.
2는 유일한 짝수 소수이므로 true를 반환합니다.
그 외의 숫자는 2부터 n-1까지 차례대로 나누어 보고, 한 번이라도 나누어 떨어지면 약수가 존재하는 것이므로 false를 반환합니다.

2. nearestPrime() 함수

while (!isPrime(++num)) {}; 구문은 핵심 부분입니다. 전위 증가 연산자(++num)를 통해 먼저 값을 1 증가시킨 후 소수인지 검사하고, 소수가 아닌 동안에는 계속 반복합니다. 소수를 만나는 순간 반복문이 종료되고 해당 값이 반환됩니다.

마무리

이처럼 소수 판별 함수와 간단한 반복문만 있으면, 임의의 숫자 이후에 등장하는 첫 번째 소수를 손쉽게 구할 수 있습니다. 성능을 더 개선하고 싶다면, 소수 검사 범위를 √n까지만 확인하도록 최적화할 수도 있습니다.