골드바흐의 추측 _ 백준 6588

이번에는 소수와 관련되어서, 조금 더 심화된 내용인 골드바흐의 추측과 관련된 문제입니다.

---

골드바흐의 추측은 문제에 나온대로, "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 를 중심으로 이루어지는데요, 

 

앞서서 풀었던 문제인 소수 찾기, 구하기의 알고리즘이 다시 활용됩니다. - 해당 코드는 아래 링크에.

2020/05/16 - [백준 문제풀이] - 소수 찾기 / 소수 구하기 _ 백준 1978,1929

소수 찾기 / 소수 구하기 _ 백준 1978,1929

 

즉, 입력받은 수에서 소수인 홀수를 뺀 수 역시 소수가 되도록 하면 됩니다.

 

이렇게 쓰니까 좀 헷갈리는데, 입력된 수가 a고 소수를 넣은 배열이 prime 이라면 prime[j]가 소수니까 a - prime[j] 역시 소수여야한다. 로 계산하면 됩니다.

 

사실 이 문제를 풀때, 에러가 좀 났었는데요, check와 prime을 main함수 안에 넣었더니 overflow가 나더라고요. 

 

main함수 바깥으로 빼고나니 해당 오류가 사라졌는데, 아마 배열의 크기가 크다보니 메모리 부족의 문제가 아닐까.. 합니다.

 

#include <iostream>
#include <cstdio>
using namespace std;
int pn = 0;
bool check[1000001];
int prime[1000000];
int main(void)
{

    check[0] = check[1] = true;
    for (int i = 2; i * i < 1000000; i++)
    {
        if (check[i] == false)
        {
            prime[pn++] = i;
            for (int j = i * 2; j <= 1000000; j += i)
                check[j] = true;
        }
    }

    while (true)
    {
        int a = 0;
        scanf("%d", &a);
        if (a == 0)
            break;
        for (int j = 1; j < pn; j++)
        {
            if (!check[a - prime[j]])
            {
                printf("%d = %d + %d\n", a, prime[j], a - prime[j]);
                break;
            }
        }
    }
    return 0;
}