728x90

https://www.acmicpc.net/problem/9020

 

9020번: 골드바흐의 추측

문제 1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

www.acmicpc.net

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	bool arr[10001] = { false };
	vector<int> primeNumber;
	arr[1] = true;
	for (int i = 2; i <= 10000; i++) {
		if (!arr[i]) {
			primeNumber.push_back(i);
			for (int j = 2; ; j++) {
				if (j * i > 10000) break;
				arr[i * j] = true;
			}
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		int a, b;
		for (int j = 0; j < primeNumber.size(); j++) {
			if (primeNumber[j] > num / 2) break;
			if (!arr[num - primeNumber[j]]) {
				a = primeNumber[j];
				b = num - primeNumber[j];
			}
		}
		cout << a << " " << b << '\n';
	}
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2752번 세수정렬  (0) 2020.03.03
[백준] 3896번 소수 사이 수열  (0) 2020.03.03
[백준] 5337번 웰컴  (0) 2020.03.01
[백준] 1011번 Fly me to the Alpha Centauri  (0) 2020.03.01
[백준] 9252번 LCS 2  (0) 2020.03.01

+ Recent posts