[BOJ / 백준] 9020번 골드바흐의 추측 C++ 문제 풀이

단계별로 풀어보기 - 수학 2단계 - [5단계] 9020번

문제

문제 링크 : www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

입력 복사 : 

3 8 10 16

 

CODE

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int i) {
	int rt;
	rt = sqrt(i);
	if (rt == 1 && i != 1) {	//2,3인 경우
		return true;
	}
	if (i % 2) {	//홀수일 경우
		for (int j = 2; j <= rt; j++) {
			if (!(i%j))
				return false;
			if (j == rt) {
				return true;
			}
		}
	}
}

int main() {
	int T;
	cin >> T;

	for (int test_case = 0; test_case < T; test_case++) {
		int n;
		cin >> n;

		for (int i = n / 2; i >= 2; i--) {
			if (isPrime(i) && isPrime(n - i)) {
				cout << i << " " << n - i << '\n';
				break;
			}
		}
	}
}

 

풀이

지난 소수 관련 문제와 동일한 방식을 이용하여 소수 여부를 리턴하는 isPrime함수를 만들었다.

두 수의 차이가 가장 작은 골드바흐 파티션을 구해야 하기 때문에,

n의 중앙값부터 2까지 감소시키며 두 수 모두 소수인지를 검사하였다.

 

결과