알고리즘 문제
[백준] 9020번 골드바흐의 추측
feelcoding
2020. 3. 3. 00:30
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