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

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

---

문제 접근

 1. 입력받은 숫자가 짝수면 반복을 시작

 2. 입력받은 숫자(n)의 반부터 시작해서 하나씩 숫자를 늘려 처음 찾은 소수(j)와 n-j가 소수인지 확인

느낀점

처음에는 되게 난해했지만 이미 골드바흐의 추측대로 소수+소수가 우리가 입력한 숫자라는 사실과 입력받은 숫자의 반에서 가장 가까운 소수가 그 소수를 뺀 값이 결국 두 수 차이의 최소라는 점을 이해해서 생각보다 쉽게 풀었다. 하지만 처음에 j만 소수인지 판별했다가 틀렸다. 이후 j와 n-j 모두 소수인지 확인하고 제출했더니 맞았다! 소수 문제가 계속 나온다고 불평했는데 생각보다 재밌게 풀었다.

코드

#include <stdio.h>

bool isPrime(int n) {
	if (n <= 1) return false;
	for (int i = 2;i * i <= n;i++) {
		if (n % i == 0) return false;
	}
	return true;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0;i < T;i++) {
		int n, j;
		scanf("%d", &n);
		if (n % 2 == 0) {
			for (j = n / 2;j < n;j++) {
				if (isPrime(j)&&isPrime(n-j)) {
					printf("%d %d\n", n-j,j);
					break;
				}
			}
		}
	}
	return 0;
}