소수 구하기

소수(Prime Number)

1은 자연수이지만, 소수도 아니고 합성수도 아니다.

소수란 1보다 큰 자연수 중에서, 양의 약수가 1과 자기 자신만 있는 수를 의미한다.

알고리즘 문제에서는 보통 주어진 정수의 소수 판별, 주어진 범위 혹은 순열 내 소수 구하기 또는 소수의 개수 세기와 같은 형태로 등장하며, 문제를 풀기 위해 소수 판별법과 소수를 구하는 알고리즘을 활용하게 된다.

합성수(Composite Number)

1보다 큰 모든 정수는 소수이거나 합성수이다.

합성수란 1보다 큰 자연수 중에서 소수가 아닌 수로, 약수의 개수가 3개 이상이고 둘 이상의 소수를 곱한 자연수이다.

소수 판별법

일반적으로 n이 비교적 작은 알고리즘 문제에서는 정확성을 위해 결정론적 방법을 사용하곤 한다.

• 결정론적 방법(deterministic method)
• 확률론적 방법(probabilistic method)

소수 판별법은 주어진 자연수 n이 소수인지 아닌지를 판별하는 알고리즘이다. 소수 판별법은 크게 결정론적 방법과 확률론적 방법으로 나뉘며, 소수 판별의 정확성과 효율성 측면에서 차이가 있다.

결정론적 방법은 수학적으로 정확한 방식으로 나온 결과가 정확하게 소수이거나 합성수임을 보장한다.

그에 반해, 확률론적 방법을 이용해서 나온 결과가 합성수이면 어떤 자연수 n은 합성수이지만, 결과가 소수로 나오더라도 반드시 소수임을 보장하지 않는다. 따라서, 결과가 소수이면 이 수는 확률적 소수(Probable prime)가 된다.

대표적인 소수 판별법

• 기본적인 소수 판별법 → 결정론적 방법
• 밀러-라빈 소수 판별법 → 확률론적 방법
• AKS 소수 판별법 → 결정론적 방법

기본적인 소수 판별법 (naive approach (=Trial Division))

n을 2부터 n-1까지의 수로 나누기

function isPrimeNumber(n){
    for(let i = 2; i < n; i++){
        // ✅ 약수를 발견하거나 (n이 합성수라는 것을 증명)
        if(n % i === 0) return false;
    }
    // ✅ 약수를 발견하지 못하거나 (n이 소수라는 것을 증명)
    return true;
}

의사코드(pseudo code)

• i를 2부터 n-1까지 1씩 증가시키며 반복한다.

  • 만약 n % i == 0 이면, false를 리턴한다.

• 반복이 끝날 때까지 약수를 찾지 못했다면 true를 리턴한다.

기본적인 소수 판별법은 단순 나눗셈을 반복하여 입력된 숫자가 소수인지 아닌지를 정확하게 판별한다. 위와 같이 작성하는 경우 시간 복잡도는 O(n)으로, 모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 매우 비효율적이다.

개선된 소수 판별법

n을 2부터 n의 정수 제곱근까지의 수로 나누기

function isPrimeNumber(n){
    let sqrt = Math.floor(Math.sqrt(n));
 
    // ✅ n의 정수 제곱근까지만 반복
    for(let i = 2; i < sqrt; i++){
        if(n % i === 0) return false;
    }
 
    return true;
}

의사코드(pseudo code)

• n의 정수 제곱근을 구한다.

• i를 2부터 n의 제곱근까지 1씩 증가시키며 반복한다.

  • 만약 n % i == 0 이면, false를 리턴한다.

• 반복이 끝날 때까지 약수를 찾지 못했다면 true를 리턴한다.

개선된 소수 판별법은 단순 나눗셈을 반복하여 소수를 판별하는 기본 원리는 유지하면서, 약수의 성질을 이용하여 확인 범위를 n의 정수 제곱근까지로 축소하여 효율성을 높였다. 이렇게 함으로써 불필요한 반복이 줄어들며 시간 복잡도 또한 O(√n)으로 개선된다.

약수의 성질

약수의 성질이란, 모든 약수가 곱셈 연산에 대해 대칭을 이루는 것을 의미한다. 예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12 로, 각각 1 * 12, 2 * 6, 3 * 4와 같이 대칭적으로 나눠진다.

이때, 제곱수의 경우 제곱근(가운데 약수)는 약수 중에서 유일하게 짝을 이루지 않는다. 예를 들어, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 으로, 이 중에서 6은 자기 자신과 곱해져서 유일하게 짝을 이루지 않는 약수가 된다.

[TODO] 밀러-라빈(Miller-Rabin) 소수 판별법

소수를 구하는 알고리즘

소수 판별법은 주어진 하나의 자연수 n이 소수인지 아닌지를 판별하는데 초점이 맞춰져있다면, 소수를 구하는 알고리즘은 주어진 자연수 n 이하의 모든 소수를 찾거나, 범위 내 소수 집합을 효율적으로 생성하는데 초점을 둔다.

소수를 구하는 알고리즘은 "걸러내기"라는 아이디어에 기반, 소수를 찾는 것이 아니라, 합성수를 제거하는 방식으로 작동하며, 주어진 범위 내의 소수 집합을 효율적으로 생성한다.

대표적인 소수를 구하는 알고리즘

• 에라토스테네스의 체
• 오일러의 체

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

2부터 시작하여 소수의 배수(합성수)를 제거

구현

function sieve(n){
    const sqrt = Math.floor(Math.sqrt(n));
    const isPrime = new Array(n + 1).fill(true).fill(false, 0, 2);  // 0, 1은 제외
 
    for(let i = 2; i <= sqrt; i++){
        if(isPrime[i]){
            // ✅ i가 소수일 때, i의 배수에 해당하는 숫자들을 거른다.
            for(let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
 
    return isPrime.reduce((primes, isPrime, i) => {
        if (isPrime) primes.push(i);
        return primes;
    }, []);
}

의사코드(pseudo code)

• n의 정수 제곱근을 구한다.

• 크기가 n + 1인 소수 판별 배열을 생성하고, 모든 값을 true로 초기화한다.

  • 0, 1은 소수가 아니므로, 배열의 0번째와 1번째 인덱스의 값을 false로 설정한다.

• i를 2부터 n의 제곱근까지 1씩 증가시키며 반복한다.

  • 만약 배열의 i번째 값이 true이면,
    • i의 배수에 해당하는 인덱스의 값을 false로 설정한다.

• 배열에서 값이 true인 인덱스를 수집하여 소수 배열을 리턴한다.

에라토스테네스의 체는 2부터 시작하여 소수의 배수(합성수)들을 걸러내는 방식으로 주어진 범위 내의 소수를 찾는 알고리즘이다.

이 과정에서 소수 판별을 위한 n + 1 크기 불리언 배열 생성이 필요하기 때문에 n의 크기가 큰 경우 메모리 사용량에 주의해야한다. 예를 들어, n = 10^7 이라면 크기가 10^7 + 1인 배열 생성이 필요하며, 이는 약 80MB로 일반적인 코딩 테스트 환경에서 허용 가능한 수준이다. 그러나 n = 10^9 일 경우, 배열 크기는 약 8GB에 달해 대부분의 코딩 테스트 환경에서 사용이 불가능하다.

에라토스테네스의 체의 시간 복잡도는 O(n · log log n) 으로 주어진 하나의 자연수 n이 소수인지 아닌지를 판별하는데에는 O(√n) 시간 복잡도를 가진 기존의 소수 판별법보다 느릴 수 있지만, 한 번 실행하여 n 이하의 소수 집합을 생성하면, 이후의 n 이하의 수가 소수인지 판별하는 작업은 O(1)로 빠르게 처리되므로, 여러 개의 소수 판별 작업이 필요한 경우 특히 적합하다.

오일러의 체 (Euler Sieve (= Linear Sieve))

모든 합성수를 한 번만 처리

구현

function sieve(n){
    const primes = new Array();
    const spf = new Array(n + 1).fill(0);
 
    for(let i = 2; i <= n; i++){
        if(spf[i] === 0){
            spf[i] = i;
            primes.push(i);
        }
 
        for(let j = 0; j < primes.length; j++){
            // ✅ 체의 범위를 초과하면 종료
            if(i * primes[j] > n)  break;
            spf[i * primes[j]] = primes[j];
            if(i % primes[j] === 0) break;
        }
    }
 
    spf.splice(0, 2);
 
    return { primes, spf };
}

의사코드(pseudo code)

• 소수를 저장할 빈 배열을 생성한다.

• 0부터 n까지 각 숫자에 대한 최소 소인수를 저장할 크기가 n + 1인 배열을 생성하고, 모든 값을 0으로 초기화한다.

• i를 2부터 n까지 1씩 증가시키며 반복한다.

  • 만약 소인수 배열의 i번째 값이 0이면,

    • 소인수 배열의 i번째 값을 i로 설정한다.
    • 소수 배열에 i를 추가한다.

  • j를 0부터 소수 배열의 길이보다 작을 때 까지 1씩 증가시키며 반복한다.

    • 만약 i와 소수 배열의 j번째 값을 곱한 값이 n보다 크다면, 체의 범위를 초과하므로 종료한다.
    • 소인수 배열의 i * primes[j]번째 값을 primes[j]로 설정한다.
    • 만약 i와 소수 배열의 j번째 값을 곱한 값이 0이라면, 이미 i의 소인수이므로 중단한다.

• 소인수 배열에서 유효하지 않은 값(0과 1)을 제거한다.

• 소수 배열과 소인수 배열을 리턴한다.