[백준 알고리즘] 9020번 : 골드바흐의 추측

문제

9020번 : 골드바흐의 추측

9020번: 골드바흐의 추측

내가 작성한 코드(C++ 성공)

#include <iostream>

using namespace std;

int main() {
	cin.tie(0);
	
	int T, N;
	int h, t;
	int check;
	
	cin >> T;
	
	for(int i=0; i<T; i++) {
		h = 0;
		t = 0;
		check = 0;
		
		cin >> N; // 8
		
		h = N/2; // 4
		t = N-h; // 4
		
		while(h > 0) {
			//cout << "h = " << t << " / t = " << t << "\n";
		
			for(int j=2; j<h-1; j++) {
				if(h%j == 0 || t%j == 0) {
					check++;
				}
			}
			
			//cout << "check =" << check << "\n";
			
			if(check >= 1) {
				h--;
				t++;
				check = 0;
			} else {
				break;
			}
		}
		
		//cout << "result = " << h << " " << t << "\n";
		cout << h << " " << t << "\n";
	}
	
	return 0;
}

 

정리

문제를 간단하게 말하자면 짝수를 입력 받아 소수 2개로 나타내는 문제다.
차이가 가장 적은 소수 2개로 표현해야 했기 때문에 가장 차이가 적어지려면 반으로 나누어서 2개로 쪼개야했다.

예를 들어, 8 이란 짝수를 입력 받았다고 하자.
8을 반으로 나누면 4, 4 이렇게 나온다.
그리고 나서 반으로 나눈 2개의 숫자가 소수인지 아닌지 판별한다.
여기서 소수인지 아닌지 판별하는 방법은 다양한데
소수는 1과 자기 자신의 수로 이루어진 수라고 부르니까
2 부터 (자기자신의 수 -1) 까지 나누어서 나머지가 0이 되는지 안 되는지 확인 했다.

for(int j=2; j<h-1; j++) {
	if(h%j == 0 || t%j == 0) {
		check++; // 나머지가 0이 되는 경우 카운트
	}
}

나머지가 0이 되는 경우가 생긴다면 두 숫자의 합이 같아야 하기 때문에
앞의 숫자에서 -1, 뒤의 숫자에서 +1 을 해주고 반복했다.

if(check >= 1) { // 나머지가 0 이 되는 경우가 있다면
	h--; // 앞의 숫자에서 -1
	t++; // 뒤의 숫자에서 +1
	check = 0; // 초기화
} else {
	break; // 나머지가 0이 되는 경우가 없다면 반복문을 빠져나간다.
}