백준
백준9020 - 골드바흐의 추측
개발하는꼬마
2020. 2. 10. 15:27
https://www.acmicpc.net/problem/9020
9020번: 골드바흐의 추측
문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
www.acmicpc.net
40000까지의 소수를 구하고 입력 받은 수 num을 반 나눠서 한쪽은 1씩 더하고 한쪽은 1씩 뺀다. 시작은 num / 2부터 하는데 뒤에서부터 구하면 처음에 구한 답이 가장 두 수의 차가 작기 때문이다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int mat[40001];
//에라토스테네스 체를 이용하여 소수 구하기
void func() {
for (int i = 1; i <= 40000; i++) {
mat[i] = i;
}
for (int i = 2; i <= 40000; i++) {
if (!mat[i]) {
continue;
}
for (int j = i + i; j <= 40000; j += i) {
mat[j] = 0;
}
}
}
int main() {
func();
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
for (int i = num / 2; i >= 2; i--) { //반 나눠서 뒤에서 부터 구하면 처음으로 조건에 성립한 값이 답이다.
int x = num - i;
int y = num - x;
if (mat[x] && mat[y]) { //소수이면
printf("%d %d\n", y, x); // 작은 것부터 출력
break;
}
}
}
}