[알고리즘] 소수 관련(에라토스테네스의 체, 골드바흐 추측)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

 

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EA%B3%A8%ED%8A%B8%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

골트바흐의 추측 - 위키백과, 우리 모두의 백과사전

 

 

1. 에라토스테네스의 체(범위 내 소수 판별)

 소수(1과 자기 자신만을 약수로 가지는 수)는 수학에서 자주 등장하는 개념이며, 코딩 테스트에서도 소수를 구하는 문제가 간간히 등장하곤 합니다. 에라토스테네스의 체는 특정 범위 안의 소수들을 마치 체에 거르듯이 찾아내는 알고리즘입니다. 

 

 에라토스테네스의 체에서 사용되는 주요 개념은 다음과 같습니다.

 

1) 자연수 n이 소수인지 판별하려면, n의 제곱근까지만 검사하면 된다.

 어떤 수가 1과 자기자신 외의 수로 나뉘어 떨어진다는 것은, 1＜a ≤ b＜n 을 만족하는 a, b의 쌍이 존재한다는 뜻입니다. 그리고 a로 나누어 떨어진다는 것은 당연히 b로 나누어 떨어진다는 것과 동일하므로, a만 검사해도 나누어 떨어지는 모든 케이스를 검사할 수 있습니다. 그리고 a가 가장 큰 케이스는 a = b, 즉 a가 n의 제곱근인 경우입니다.

 

2) 소수를 찾았다면, 해당 소수의 배수는 모두 소수가 아니다.

 당연한 얘기지만 소수의 2 이상의 배수는 모두 소수가 아닙니다. 예를 들어 3은 소수지만, 3의 2 이상의 배수들(6, 9, 12, ...) 은 모두 3으로 나뉘어 떨어지므로 소수가 아닙니다. 따라서 에라토스테네스의 체에서는 주어진 범위만큼의 배열을 선언해두고, 2부터 시작하여 다음으로 찾은 소수의 배수들을 전부 소수가 아닌 것으로 판단하여 걸러냅니다. 

 

 

 다음은 에라토스테네스의 체를 사용하여 1부터 N까지의 숫자 중에서 소수를 찾아서 출력하는 코드 예시입니다.

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

void eratosthenes(int N)
{
    // 숫자를 바로 인덱스로 사용하기 위해 N + 1 사이즈로 선언
    vector<bool> is_prime(N + 1, true);

    // N의 제곱근까지 검사하므로 미리 계산
    const int limit = static_cast<int>(sqrt(N));
    for(int i = 2; i <= limit; ++i)
    {
        // 앞에서 이미 걸러졌다면 소수가 아니므로 스킵
        if (false == is_prime[i])
            continue;

        // i보다 작은 배수들은 앞에서 이미 걸러지므로 i * i부터 시작
        // i의 배수들을 걸러야하므로 i씩 증가
        for(int j = i * i; j <= N; j += i)
            is_prime[j] = false;
    }

    // 2부터 시작해서 살아 남은 숫자들을 출력
    for (int i = 2; i < N + 1; ++i)
        if (is_prime[i])
            cout << i << " ";
    cout << endl;
}

int main()
{
    int N;
    cout << "숫자를 입력하세요: ";
    cin >> N;

    cout << N << "이하의 소수들은 다음과 같습니다.\n";
    eratosthenes(N);
}

사진 1. 에라토스테네스의 체

 

 우선 N + 1 크기의 bool 벡터(혹은 배열)를 선언합니다. N + 1 크기인 이유는 숫자 값을 곧바로 인덱스로 편하게 사용하기 위함이며, 최초의 소수인 2 아래로는 사용하지 않습니다. 그리고 반복문을 돌며 i의 배수들을 전부 걸러내는데, 이 때 검사 상한은 위에서 언급했듯이 N의 제곱근입니다. 미리 선언해 둔 bool 벡터를 체크하여 이미 걸러지지 않았는지(소수인지) 확인하고, 소수가 맞다면 2중 반복문을 돌며 i의 배수들을 걸러냅니다. 여기서 j = i * i에서 시작하는데, 이는 i보다 작은 배수는 이미 이전 과정에서 걸러지기 때문입니다. 예를 들어 5의 경우, 25보다 작은 10, 15, 20은 이미 2와 3의 배수를 걸러내는 과정에서 처리됩니다. 따라서 j = i * i에서 시작하여 i만큼씩 증가하며 N까지 검사합니다. 

 

 이렇게 모든 검사가 끝난 후, bool 벡터를 인덱스 2부터 순회하며 값이 true라면 소수임을 확인할 수 있습니다. 사진 1은 해당 코드를 통해 1부터 100까지의 소수들을 찾아내어 출력한 결과입니다.

 

 

2. 골드바흐 추측(짝수는 두 소수의 합)

 골드바흐 추측이란 2보다 큰 모든 짝수는 두 소수의 합으로 표현할 수 있다는 내용으로, 이름에서 알 수 있듯이 아직 완벽하게 증명된 내용은 아닙니다. 다만 슈퍼컴퓨터를 통해 약 몇백경 이하의 숫자에서 성립한다는 것이 확인되었으므로, 통상적으로 사용되는 숫자 범위 내에서는 통용된다고 볼 수 있겠습니다. 작은 숫자들을 예로 생각해보면 10 = 3 + 7, 24 = 11 + 13, 48 = 17 + 31 등으로 성립하는 것을 확인할 수 있습니다.

 

 사실 엄밀히 따지자면 골드바흐의 추측은 강한 추측과 약한 추측으로 나뉘며, 약한 추측 쪽은 증명이 되었다는 얘기가 있습니다. 다만 골드바흐의 추측은 유명한 수학계의 난제 중 하나로, 이에 관한 책들도 여러권 있을 정도이므로 여기서는 깊게 파고들지 않겠습니다. 일단 통상적으로 사용하는 숫자 범위 내에서 짝수는 두 소수의 합으로 표현 가능하다(중복 허용) 정도로 정리하겠습니다.

 

 

3. 서로 다른 두 소수의 합으로 표현 가능한지 검사

 어떤 자연수가 서로 다른 두 소수의 합으로 표현 가능한지 검사하려면 짝수/홀수의 특징과 소수의 특징, 그리고 골드바흐 추측을 모두 활용해야 합니다. 우선 서로 다른 두 소수의 합으로 표현 가능한 최초의 자연수는 5 (2 + 3)이므로, 5보다 작은 숫자는 검사할 필요 없이 거짓입니다. 5 이상의 숫자에 대해서는 다음과 같이 3가지 케이스가 존재합니다.

 

 

1) 홀수인 경우

 두 숫자의 합이 홀수가 되려면 짝수 + 홀수여야 하며, 소수 중 짝수는 2가 유일합니다. 따라서 홀수 n이 서로 다른 두 소수의 합이 되려면 2 + (n - 2)의 형태만 가능하고, 여기서 (n - 2)가 소수여야 합니다. 즉, 홀수인 경우 n - 2가 소수인지 여부에 달려있습니다.

 

2) 짝수이며, 2로 나눈 값이 소수가 아닌 경우

 골드바흐 추측에 따라 2보다 큰 짝수는 모두 소수의 합으로 표현할 수 있습니다. 그리고 2로 나눈 값이 소수가 아니라면, 같은 소수를 2번 더해서 골드바흐 추측을 만족하는 경우도 아니므로 서로 다른 두 소수의 합으로 표현 가능합니다.

 

3) 짝수이며, 2로 나눈 값이 소수인 경우

 해당 케이스는 서로 다른 두 소수의 합인지 쉽게 판단할 수 없습니다. 예를 들면 14의 경우, 2로 나눈 값이 7이이므로 7 + 7이라는 같은 소수의 합으로 표현됨을 알 수 있지만, 3 + 11처럼 서로 다른 두 소수의 합으로도 표현 가능하기 때문입니다. 따라서 이 경우에는 가능한 모든 합을 검사해야 합니다(단, 같은 숫자의 합은 제외). 

 

 

다음은 위 내용을 적용한 코드 예시입니다.

#include <iostream>
#include <math.h>

using namespace std;

// 소수 판별 함수
bool is_prime(const int num)
{
    const int limit = static_cast<int>(sqrt(num));
    for (int i = 2; i <= limit; ++i)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

bool check_condition(const int value)
{
    // 서로 다른 두 소수의 합으로 표현 가능한지 검사
    // 최소 5부터 조건을 만족하므로 5 미만은 스킵
    if (value < 5)
        return false;

    // 홀수인 경우, 짝수 + 홀수로만 표현 가능하므로 소수 중 유일한 짝수인 2와 value - 2가 소수인 경우에만 조건 만족
    if ((value & 1) == 1)
        return is_prime(value - 2);

    // 짝수인 경우 2보다 크다면 모두 소수의 합으로 표현 가능하지만, 골드 바흐 추측은 중복을 허용
    // 2로 나눈 값이 소수가 아니라면 서로 다른 두 소수의 합으로 표현 가능
    if (false == is_prime(value / 2))
        return true;

    // 2로 나눈 값이 소수라면 골드 바흐 추측만으로 완벽하게 판단할 수 없음(ex. 14 = 3 + 11 = 7 + 7)
    // => 짝수 중 2로 나눈 값이 소수인 경우만 모든 경우의 수를 검사
    int small = 2, big = value - 2;
    bool sum_prime = false;
    while (big > small)
    {
        if (is_prime(big) && is_prime(small))
        {
            sum_prime = true;
            break;
        }
        --big;
        ++small;
    }
    return sum_prime;
}

int main()
{
    int value;
    cout << "자연수를 입력하세요: ";
    cin >> value;

    if (check_condition(value))
        cout << value << "는(은) 서로 다른 두 소수의 합입니다." << "\n";
    else
        cout << value << "는(은) 서로 다른 두 소수의 합이 아닙니다." << "\n";
}

사진 2. 서로 다른 두 소수의 합인지 검사