[수학] 골드바흐의 추측 (백준 6588번)

바흐는 아는데 골드바흐는 처음 들었다.

그래서 알아보니까, 오일러의 친구였나보다.

골드바흐는 소수에 관한 추측들을 했는데, 이하 생략하고 그 중 하나로서 다음과 같은 추측을 해보았다.

 

"4보다 큰 모든 짝수는 두 홀수 소수(2를 제외한 소수들)의 합으로 나타낼 수 있다."

 

사실 미해결된 명제이기도 하거니와,

소수를 구하는 공식도 결국 다 때려박기라 소수의 끝도 모르는데 저게 증명될 일이 있을까.

코딩러들은 이 문제를, brute force로 해봐서 모든 경우의 수가 성립함을 알 수 있을 것이다.

물론 long long int 범위 내에서... 수학은 근데 귀납을 인정 안하니 프로그래머들에겐 불가능하겠다.

 

(빌게이츠는 세계적인 수학 난제도 증명도 했다던데?)

(그 땐 빌게이츠도 프로그래머가 아니라 법대생이니까 논외. / 뭐?)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
#define Max 1000000
int arr[Max + 1];
 
bool check(long long int testNum)
{
    for (long long int i = 2; i <= testNum / 2; i++)
    {
        if (testNum % i == 0)
        {
            return false;
        }
    }
    return true;
}
 
void eratos()
{
    for (int i = 2; i <= Max; i++)
        arr[i] = true;
 
    for (int i = 2; i * i <= Max; i++)
    {
        if (arr[i])
            for (int j = i * i; j <= Max; j += i)
            {
                arr[j] = false;
            }
    }
}
 
int main(void)
{
    eratos();
    // 일단 소수인지 아닌지 모든 숫자를 미리 판별하는 게 차라리 빨리 푸는 방법이었다.
    // 에라토스테네스의 체 방식으로, 어떠한 숫자가 소수라면,
    // 그 배수들은 모두 소수가 아니라고 미리 정의하는 방식으로 진행한다.
    // 재귀에서 memorization을 쓰는 것과 같이, 미리 다 구해놓는 것이 훨씬 낫다.
    
    // 이 문제는, 시간초과만 극복하면 사실 어려울 게 없다.
 
    long long int num = 1;
 
    while (num != 0)
    {
        scanf("%lld", &num);
 
        for (long long int i = 3; i <= num / 2; i += 2)
        {
            // if (check(i))로 대체할 수 있긴 하다.
            // 이 함수는 내가 이전에 만든 함수인데, 소수인지 아닌지 알아내는 함수다.
            if (arr[i])
            {
                // if (check(num - i))
                if (arr[num - i])
                {
                    printf("%lld = %lld + %lld\n", num, i, num - i);
                    break;
                }
            }
        }
    }
}
// 솔직히, test case가 무진장 많다는 것을 미리 말해줬으면,
// 내가 시간초과를 여러 번 겪지 않고 바로 memorization을 응용해서 풀었을 것이다.
 
// 억울하다.

 

느낀 점

 

최대 공약수나 소수나, 의외로 이런 부분이 매우 어렵다.

단순히 전체탐색을 진행해 풀 수 있는 문제들이지만, 시간초과나 메모리 제한이 걸리면 어려워진다.

또, 봐도 이해가 되지 않는 부분도 있다. (수학적인 영역에, 더 능력을 키워야 할지도 모르겠다.)

이건 최대공약수의 이야기지만, 특정 최대공약수 a의 모든 약수를 구할 때,

어떻게 해야 모든 약수를 빠르게 구할 것인가,

for (int i = 1; i <= a; i++) 라는 형식으로 탐색을 해도 좋고

for (int i = a; i >= a/2; i--) 라는 형식의 탐색 후에 1만 따로 출력해도 좋고

양쪽 항의 곱이 항상 일정하다는 것을 이용해서 좋다.

제곱근을 이용한 괴랄한 방식도 있었는데, 이건 솔직히 왜 효율적인지 아직도 모르겠다.

 

의외로, 나중에 이런 수학적인 부분이 내 발목을 잡을지도 모르겠다. (난 높이 가고 싶은데.)