[C++] 백준 9020번: 골드바흐의 추측

문제 이해하기

골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표현될 수 있다는 것이다. 나는 모든 짝수는 2로 나누어진다는 것을 이용해 2로 나눈 값에서 하나는 차례로 1을 빼면서, 다른 하나는 차례로 1을 더해가면서 두 수가 모두 소수가 될 때를 찾아내는 방식을 문제를 풀었다.

 

코드로 표현하기

#include <iostream>

using namespace std;

bool isit(int x) {
	if (x < 2) return false;
	for (int i = 2; i < x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

int main() {
	int t, n;
	int a, b;
	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;
		
		a = n / 2;
		b = n / 2;
		while (1) {
			if (isit(a) && isit(b)) {
				cout << a << " " << b << endl;
				break;
			}
			a -= 1;
			b += 1;
		}
	}
}

더했을 때의 값이 짝수 n을 이루는 두 소수를 각각 a와 b라고 한다. 먼저 짝수 n을 2로 나누었을 때 값이 소수인지 확인하고 소수라면 그 값을 그대로 출력한다. 소수가 아니라면 a는 1씩 작게 하고, b는 1씩 크게 하면서 a와 b가 동시에 소수가 될 때를 찾아 그때의 값을 결과로 출력한다.