[백준 / C언어] Day41. 골드바흐의 추측 (6588)

2024. 07. 14 - 코딩테스트 스터디 Day41

 

 

01. 문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

 

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

02. 입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

 

 

03. 출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

 

04-1. 예제 입력 1

8
20
42
0

 

 

04-2. 예제 출력 1

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

 

 

05. 풀이 및 답

소수는 1과 자기 자신 외의 수로는 나누어 떨어지지 않는 1보다 큰 정수이다.

 

#include <stdio.h>

int main() {
    int n, prime[1000001];
    
    for (int i = 2; i < 1000001; i++) {
        prime[i] = 1;
    }
    
    for (int i = 2; i * i < 1000001; i++) {
        if (prime[i]) {
            for (int j = i * i; j < 1000001; j += i) {
                prime[j] = 0;
            }
        }
    }
    
    while (1) {
        scanf("%d", &n);
        if (n == 0) break;
        
        int goldbach = 0;
        
        for (int j = 3; j <= n / 2; j += 2) {
            if (prime[j] == 1 && prime[n - j] == 1) {
                printf("%d = %d + %d\n", n, j, n - j);
                goldbach = 1;
                break;
            }
        }
        if (goldbach == 0) printf("Goldbach's conjecture is wrong.\n");
    }
    
    return 0;
}

우선 소수 판별을 하기 전, 소수 여부를 나타내는 prime 배열을 모두 1로 초기화하였다. 모든 수를 소수로 가정하고 시작하는 것이다.

 

이번 문제에서는 소수 판별을 위해 '에라토스테네스의 체'를 사용하였다.

i가 소수일 경우, i를 제외한 i의 배수들을 모두 소수가 아닌 것(0)으로 처리한다.

 

입력받은 n이 0이면 반복문을 빠져나가 프로그램을 종료한다.

 

n에 대해 j와 n - j가 모두 소수인지 검사한다.

j와 n - j 모두 소수면, 두 홀수 소수의 합이 n이 되는 것이기 때문에 변수 goldbach를 1로 설정한다. 

 

모든 범위에서 합이 n인 두 홀수 소수를 찾지 못했다면, goldbach가 0이므로 "Goldbach's conjecture is wrong."이라는 문구를 출력한다.

 

 

💎 에라토스테네스의 체 💎

에라토스테네스의 체는 가장 간단하고 빠르게 소수를 찾는 방법이다.
개념을 간단하게 설명하자면

1. 1을 제거
2. 2를 제외한 2의 배수 제거
3. 3을 제외한 3의 배수 제거
4. 5를 제외한 5의 배수 제거 (4의 배수는 2의 배수에서 다 지워짐)
5. 7을 제외한 7의 배수 제거
...

위와 같은 단계를 거쳐 판별하는 것이다.

 

 

정답!

 

---

너무 어렵다