[JS] 소수찾기

Yongmin Park·2024년 7월 21일

JS-Programmers

목록 보기

12/14

여러분, 혹시 소수(prime number)라는 개념을 들어보신 적 있으신가요? 소수는 수학적 개념 중에서도 꽤 흥미로운 주제인데요. 오늘은 이 소수를 빠르게 찾아내는 방법 중 하나인 '에라토스테네스의 체(Sieve of Eratosthenes)'에 대해 이야기해 볼까 합니다. 그럼 문제를 통해 이 개념을 어떻게 적용할 수 있는지 자세히 알아보도록 할게요.

문제 설명

오늘 다룰 문제는 "1부터 n까지의 숫자 중에서 소수의 개수를 반환하라"는 것입니다.

소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 수를 의미합니다. 예를 들어, 2, 3, 5, 7 등이 소수에 해당합니다. 반면에 10는 1, 2, 5, 10으로 나누어지기 때문에 소수가 아닙니다.

이 문제를 해결하기 위해 사용할 방법은 '에라토스테네스의 체'라는 알고리즘입니다. 이 단어가 좀 어렵게 느껴지시겠지만, 실제로는 그리 복잡하지 않습니다.

에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체는 소수를 찾는 가장 효율적인 방법 중 하나입니다. 이 방법의 아이디어는 다음과 같습니다:

2부터 시작해서 해당 숫자의 배수를 모두 제거합니다.
이후 남아있는 숫자 중에서 다음 소수를 찾아내고, 그 소수의 배수를 다시 제거합니다.
위 과정을 반복하면 주어진 범위 내에서 소수만 남게 됩니다.

이제 이 방법을 사용해 실제로 문제를 해결해보겠습니다!

구현 코드

먼저 에라토스테네스의 체 알고리즘을 코드로 어떻게 구현할 수 있는지 살펴보겠습니다.

// 전체 범위의 숫자를 소수인지 판별할 수 있는 배열로 초기화합니다.
function findPrimeCount(n) {
    // 각 숫자가 소수인지 여부를 나타내는 배열을 초기화 (true: 소수, false: 소수가 아님)
    let isPrime = new Array(n + 1).fill(true);
    // 소수가 아닌 숫자를 제외할 때 사용될 카운터 변수 초기화
    let count = 0;

    // 2부터 n까지의 숫자에 대해 소수 여부를 판별합니다.
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            count += 1; // 현재 숫자가 소수임을 확인했으므로 카운트 증가
            // 현재 소수의 배수들은 소수가 아니므로 false로 설정합니다.
            for (let j = 2 * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 소수의 개수를 반환합니다.
    return count;
}

코드 설명

이 코드는 다음과 같은 단계로 동작합니다.

먼저 isPrime이라는 배열을 초기화합니다. 이 배열의 인덱스는 각 숫자에 대응하고, 배열의 값은 해당 숫자가 소수인지 여부를 나타냅니다. 초기에는 모든 값을 true로 설정하여 모든 숫자가 소수라고 가정합니다.
2부터 시작하여 각 숫자에 대해 소수인지 확인합니다. 만약 현재 숫자가 소수라면, 해당 숫자의 배수들은 모두 소수가 아니므로 false로 설정합니다.
이 과정을 n까지 반복하며 소수의 개수를 찾아냅니다.