JavaScript로 n번째 소수 구하기 – 효율적인 함수 구현 방법

숫자 하나를 유일한 인수로 받는 자바스크립트 함수를 작성해야 합니다. 이 숫자를 n이라고 부르겠습니다. 함수는 첫 번째 소수부터 차례대로 세어 n번째 소수를 찾아 반환해야 합니다.

예시

예를 들어 n = 6이라면, 여섯 번째 소수인 13이 출력되어야 합니다.

• n = 6 → 13
• n = 16 → 53
• n = 66 → 317

코드 예제

다음은 위 요구 사항을 구현한 전체 코드입니다.

const findPrime = num => {
    let i, primes = [2, 3], n = 5;
    const isPrime = n => {
        let i = 1, p = primes[i],
        limit = Math.ceil(Math.sqrt(n));
        while (p <= limit) {
            if (n % p === 0) {
                return false;
            }
            i += 1;
            p = primes[i];
        }
        return true;
    }
    for (i = 2; i <= num; i += 1) {
        while (!isPrime(n)) {
            n += 2;
        }
        primes.push(n);
        n += 2;
    };
    return primes[num - 1];
}
console.log(findPrime(6));
console.log(findPrime(16));
console.log(findPrime(66));

출력 결과

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

13
53
317

동작 원리

이 코드가 효율적으로 동작하는 핵심 로직은 다음과 같습니다.

1. 소수 배열 초기화: 가장 작은 두 개의 소수인 2와 3으로 배열을 시작합니다.
2. isPrime 헬퍼 함수: 이미 발견된 소수들만 활용해 √n 이하의 값으로 나누어 떨어지는지 검사합니다. 불필요한 나눗셈을 줄여 성능을 크게 향상시킵니다.
3. 홀수만 검사: 2를 제외한 모든 소수는 홀수이므로, 후보 숫자를 2씩 증가시켜 짝수 검사를 아예 건너뜁니다.
4. 결과 반환: num개의 소수가 배열에 모두 채워질 때까지 반복한 뒤, 마지막 요소인 primes[num - 1]을 반환합니다.

이처럼 기존에 찾은 소수 목록을 재활용하고 검사 범위를 제곱근까지로 제한하면, 단순 무차별 대입 방식보다 훨씬 빠르게 n번째 소수를 구할 수 있습니다.