[9020번] 골드바흐의 추측

백준 9020번: 골드바흐의 추측

9020번: 골드바흐의 추측

이번에 풀어볼 문제는 "골드바흐의 추측"이라는 문제입니다.

문제를 읽기에 앞서 '골드바흐의 추측'에 대해 알아봅시다.

골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로,
2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다.
이때 하나의 소수를 두 번 사용하는 것은 허용한다.

출처) 위키백과 - 골드바흐의 추측https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

예를 들어, 4 = 2 + 2 / 6 = 3 + 3 / 10 = 5 + 5 / 12 = 5 + 7 / ... 등이 있습니다.

 

---

▶ 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다. (4 ≤ n ≤ 10,000)

▶ 출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션( ex. n = 4 일 때는 2 2 )을 출력한다.

출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

---

 

일단 이 문제는 보통 저희가 코딩을 처음하면서 접하게 되는 소수 문제 중 하나입니다.

그래서 저는 테스트 케이스를 입력받기 전에 먼저 숫자 10,000까지 소수들을 구했습니다.

 

소수를 구하는 방법에는 여러가지가 있겠지만, 제가 아는 것 중에서 가장 빠르고 간단하다고 생각되는

"에라토스테네스의 체"를 이용했습니다. ( 알고리즘은 찾아보시면 잘 설명된 블로그들이 많습니다 ^^ )

 

그렇게 소수를 구하고 실질적인 골드바흐 파티션을 구하는 방법은 다음과 같이 생각했습니다.

먼저 주어지는 자연수는 모두 짝수이니 절반으로 나누고, 그 값을 파티션의 왼쪽과 오른쪽 값으로 초기화했습니다.

그리고 나서 왼쪽 값은 하나씩 줄이며, 오른쪽 값은 하나씩 늘리며 둘 다 소수라고 판단될 때까지 반복 하였습니다.

 

다음은 위의 생각들을 정리한 코드입니다.

사용 언어: C++

#include <cstdio>
#include <cmath>
#define SIZE 10000

int net[SIZE + 2];

void make_Net() {
    net[1] = 1;
    for(int i = 2; i <= sqrt(SIZE); ++i)
        if(net[i] == 0)
            for(int j = i * 2; j <= SIZE; j += i)
                net[j] = 1;
}

int main() {
    int T;
    scanf("%d", &T);
    
    make_Net();
    
    while(T--) {
        int n;
        scanf("%d", &n);
        int l = n / 2, r = l;
        
        while(net[l] != 0 || net[r] != 0) --l, ++r;
        
        printf("%d %d\n", l, r);
    }
}

---

저는 이것으로 백준 단계별 풀어보기 '소수 구하기' 부분을 모두 풀어보았습니다.

더 좋은 방법이 있거나 틀린 점이 있다면 알려주시면 감사하겠습니다. 글 읽어주셔서 감사합니다!