JavaScript로 지정한 범위 내 임의의 소수 생성하기

두 개의 숫자를 인자로 받아 검색 범위를 지정하고, 그 범위 안에 포함된 소수 중 하나를 무작위로 골라 반환하는 JavaScript 함수를 작성해 보겠습니다.

범위 내의 모든 소수를 효율적으로 찾기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용합니다. 이 방식은 2부터 √max까지의 수에 대해 각각의 배수를 차례로 제거해 나가기 때문에, 비교적 넓은 범위에서도 빠른 속도로 소수 목록을 얻을 수 있습니다.

예제 코드

const range = [100, 1000];

// 에라토스테네스의 체로 min ~ max 사이의 소수 목록 생성
const getPrimes = (min, max) => {
    const result = Array(max + 1)
        .fill(0)
        .map((_, i) => i);
    for (let i = 2; i <= Math.sqrt(max + 1); i++) {
        for (let j = i ** 2; j < max + 1; j += i) delete result[j];
    }
    return Object.values(result.slice(min));
};

// min ~ max 사이의 임의의 정수 반환
const getRandomNum = (min, max) => {
    return Math.floor(Math.random() * (max − min + 1) + min);
};

// 소수 목록에서 무작위로 하나를 선택
const getRandomPrime = ([min, max]) => {
    const primes = getPrimes(min, max);
    return primes[getRandomNum(0, primes.length − 1)];
};

console.log(getRandomPrime(range));

코드 동작 원리

• getPrimes(min, max): 0부터 max까지의 숫자 배열을 만든 뒤, 2부터 √(max+1)까지 반복하면서 각 수의 제곱값부터 배수들을 삭제합니다. 마지막으로 min 이상의 값만 추출해 소수 배열을 반환합니다.
• getRandomNum(min, max): Math.random()과 Math.floor()를 조합해 지정된 범위 내의 임의의 정수를 생성합니다.
• getRandomPrime([min, max]): 앞의 두 함수를 연결해, 구한 소수 목록에서 인덱스를 무작위로 골라 하나의 소수를 반환합니다.

실행 결과

311

소수가 무작위로 선택되기 때문에 코드를 실행할 때마다 출력되는 값은 달라집니다. 다만 어떤 경우에도 지정한 범위(여기서는 100~1000) 안에 속한 소수만 반환됩니다.