[백준6588] 골드바흐의 추측 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int arr[10000001];
int prime[10000001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// 에라토스테네스의 체
	for (int i = 0; i < 1000001; i++) {
		arr[i] = i;
	}
	for (int i = 2; i < 1000001; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = 2; i * j < 1000001; j++)
			arr[i * j] = 0;
	}
	// 3 이상의 소수로 이루어진 배열 설정
	for (int x = 3, y=0; x < 1000001; x++) {
		if (arr[x]) {
			prime[y] = arr[x];
			y++;
		}
	}
	// 골드바흐의 추측 검증
	while (1) {
		int n;
		bool flag = false;
		cin >> n;
		if (n == 0)
			break;
		for (int z = 0;z<sizeof(prime)/sizeof(int);z++) {
			if (arr[n - prime[z]]) { // 골드바흐의 추측이 맞을 경우
				cout << n << " = " << prime[z] << " + " << arr[n - prime[z]] << '\n';
				flag = true;
				break;
			}
			if(flag=false) // 골드바흐의 추측이 틀렸을 경우
				cout << "'Goldbach's conjecture is wrong.";
		}
		
	}
	return 0;
}

골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
N(짝수)=A(소수)+B(소수)

-> A=N-B

이 추측이 맞다면 N-B는 소수여야 한다. 따라서 N-B가 소수임을 확인하면 골드바흐의 추측이 사실인지를 검증할 수 있다.

에라토스테네스의 체를 이용하여 간단하게 문제를 풀 수 있다.