JavaScript로 주어진 숫자보다 큰 가장 작은 다음 소수 찾기

문제 이해하기

이번 문제는 JavaScript 함수를 작성하는 것입니다. 함수는 하나의 숫자 n을 입력받아야 하며, n보다 큰 수 중에서 가장 작은 소수를 찾아 반환해야 합니다.

예를 들어, 101이 입력되면 101 자체가 소수이므로 그다음으로 큰 소수인 103을 반환해야 합니다.

접근 방법

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

1단계: 소수 판별 함수 — 어떤 수가 소수인지 확인합니다. 효율성을 위해 2부터 해당 수의 제곱근까지만 나누어 떨어지는지 검사하면 됩니다. 제곱근까지만 확인해도 충분한 이유는, 만약 num = a × b라면 a와 b 중 하나는 반드시 √num 이하이기 때문입니다.

2단계: 다음 소수 탐색 — 주어진 숫자부터 1씩 증가시키면서 소수가 발견될 때까지 위 판별 함수를 반복 호출합니다.

구현 코드

const num = 101;

// 소수 판별 함수
const isPrime = (num) => {
    let sqrtnum = Math.floor(Math.sqrt(num));
    let prime = num !== 1;
    for(let i = 2; i < sqrtnum + 1; i++){
        if(num % i === 0){
            prime = false;
            break;
        };
    };
    return prime;
}

// 다음 소수를 찾는 함수
const nextPrime = (num = 1) => {
    while(!isPrime(++num)){
    };
    return num;
};

console.log(nextPrime(num));

코드 설명

isPrime 함수는 먼저 입력값의 제곱근을 구한 뒤, 2부터 제곱근까지의 모든 수로 나누어 떨어지는지 확인합니다. 하나라도 나누어떨어지면 소수가 아니므로 false를 반환하고, 끝까지 통과하면 true를 반환합니다. 또한 num !== 1 조건을 통해 1은 소수가 아니라고 명확히 처리하고 있습니다.

nextPrime 함수는 전위 증가 연산자(++num)를 사용해 숫자를 먼저 1 증가시킨 후 소수인지 검사합니다. 소수가 아닌 동안은 계속 반복하고, 소수를 만나면 그 값을 그대로 반환합니다.

실행 결과

103

101 다음으로 가장 작은 소수인 103이 정상적으로 출력되는 것을 확인할 수 있습니다.