오늘의 코드. 6일차 (백준/9020번 골드바흐의 추측)

평소에 수학 관련 유튜브를 챙겨보는 중, 그중 골드바흐의 추측(Goldbach's conjecture)은 굉장히 오래된정수론에 있어 '미해결 문제'이라는 사실을 알게 되었다. 아니나 다를까, 백준에는 같은 이름의 문제가 있어
풀어보게 되었다. 

 

Baekjoon / Problem No.9020 (골드바흐의 추측)

 

Problem

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

Input

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

Output

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

---

Solution 1

골드바흐의 추측이란, 위의 문제에서도 볼 수 있듯이, "2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다." 라는 것이다.

 

그렇다면, 어떤 수 N을 받았을때, 그 숫자를 2로 나누어(짝수이므로 항상 가능하다.) 2부분으로 나누어보자.

예를들어 16을 생각해보자.

16 = 8 + 8 = 7 + 9 = 6 + 10 = 5 + 11 = ··· = 1 + 15

 

위와 같이 점점 줄어드는 부분(코드에서는 low부분)과 늘어나는 부분(코드에서는 high부분)으로 나누어 1씩 더하고 빼주면서 low부분과 high부분이 '둘 다(AND)' 소수인 부분을 판별하면 될 것이다.

 

 여기서 소수판별하는 방법에는 여러가지 방법들이 있다. 

1. 소수의 성질을 이용한 방법 1 (1과 자기자신을 제외하고 약수를 갖지 않는 성질을 의미함.) (시간복잡도 O(N))
2. 소수의 성질을 이용한 방법 2 (위 1번 + 어떤 수의 약수들이 가지는 성질을 이용) (시간복잡도 O(√N))
3. 에라토스테네스의 체를 이용한 방법 (시간복잡도 O(Nlog(logN)))
4. 밀러 - 라빈 소수 판별법 (Miller - Rabin primality test) + 고속 푸리에 변환 (시간 복잡도 O(Nlog^2N)또는 O(Nlog^3N))

"위의 여러가지 소수 판별법은 코딩 지식 게시판의 "오늘의 코딩지식. No. 2 소수판별법" 에서 추후에 자세히 다루겠다."

 

필자는 위의 문제조건들과, 시간제한(2초)를 고려하였을때, 2번째 방법(소수의 성질을 이용한 방법 2)를 이용해 보았다.

---

Code

#include <cstdio>
#include <math.h>

using namespace std;
bool isPrime(int num) {
	for (int i = 2; i <= sqrt(num); i++)
    {
		if (num % i == 0)
			return false;
	}
	return true;
}
int main()
{
    int T; // 테스트 케이스 수
    int cases; // 현재 테스트 케이스 번호
    scanf("%d", &T);

    for (int i = 0; i < T; i++)
    {
        scanf("%d", &cases);

        int low, high;
        low = high = cases/2;
        while (low > 0)
        {
            if (isPrime(low) && isPrime(high))
            {
                printf("%d %d\n", low, high);
                break;
            }
            low--;
            high++;  // low 와 high를 1씩 빼고 더해주면서, 합이 짝수인 소수쌍을 찾는다.
        }

    }
}

 

 

코드가 길어 사진은 생략하도록 하겠다.

---

Review

미해결 문제라고 들어서 훨씬 복잡한 알고리즘을 떠올렸으나, 효율성의 차이이지 사실상 간단한 문제였다. 다만, 미해결 문제에 걸맞게 배경지식 (푸리에 변환, 밀러 - 라빈 소수판별에 쓰이는 페르마의 소정리, 정수론)이 꽤나 쓰이는 부분이 있다.

빠른 시일 내에 해당 정보에 대해서는 "오늘의 코딩지식" 카테고리로 업로드 예정이니 조금만 기다려주길 바란다.