[BOJ] 백준 #9020. 골드바흐의 추측 (C++)

🎨 문제

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

• 알고리즘 분류: 소수판정, 정수론, 수학
• 난이도: Silver Ⅰ

💬 풀이

다 직접 나눠서 확인하는 방법 말고는 도저히 모르겠어서 ‘소수 판별법’을 검색해봤다.

✔소수 판별 알고리즘

1) 2부터 $N-1$까지 직접 다 나눠서 판별. => 노가다 ― $O(N)$
2) 2부터 $\sqrt{N}$까지 나눠서 판별. ― $O(\sqrt{N})$
∵ N=a×b에서 N의 제곱근까지 곱하면 어차피 대칭 형태(N=b×a)이므로.
3) 소수들의 배수를 모두 제외해주는 방법 ― $O(NloglogN)$

나는 이중에 Sol 2) ‘제곱근까지 다 나눠보고 소수인지 판별’하는 방법으로 문제를 풀었다.

1. 마지막 출력 조건에 따라 ‘출력하는 소수는 작은 것부터 먼저 출력’해야하므로 n/2부터 for문을 돌면서 a,b가 소수인지 체크한다.
2. isPrimeNum()
   👉🏻 n=1이거나 n<1이라면 소수가 아니다.
   👉🏻 n=2면 소수다.
   👉🏻 n=2를 제외한 모든 짝수는 소수가 아니다.
   👉🏻 n≥3인 홀수일 때, 2부터 n의 제곱근까지 하나라도 n%i == 0면 소수가 아니다.
   👉🏻 이외의 경우 모두 소수다.
   

👩‍💻 코드

C++

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

bool isPrimeNum(int n) {
	if (n <= 1) { return false; }
	else if (n % 2 == 0) { return n == 2 ? true : false; }
	else {
		for (int i = 3; i <= (int)sqrt(n); i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
	}
	return true;
}

int main() {
	//freopen("input.txt", "rt", stdin);
	int T;
	cin >> T;
	int* n = new int[T];
	int a = 2, b;
	for (int i = 0; i < T; i++) {
		cin >> n[i];
		for (int j = n[i] / 2; j >= 2; j--) {
			a = j;
			b = n[i] - j;
			if (isPrimeNum(a)) {
				if (isPrimeNum(b)) {
					cout << a << ' ' << b << endl;
					break;
				}
			}
		}
	}

	return 0;
}