https://www.acmicpc.net/problem/9020
문제
> 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다.
> 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다.
> 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
> 골드바흐의 추측은 유명한 정수론의 미해결 문제로,
2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.
> 이러한 수를 골드바흐 수라고 한다.
> 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
> 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다.
> 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
> 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오.
> 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.접근
n이 최대 10000까지 가능하므로 에라토스테네스의 체로 미리 10000까지의 소수를 구한다.
2부터 10000의 제곱수 까지 각각의 배수들을 각각의 제곱인 수부터 시작한다. 2의 배수는 2x2부터 시작, 3의 배수는 3x3부터 시작한다.
왜냐하면 4x3과 4x2는 각각 2와 3의 배수로 이미 처리가 됐기 때문에 4x4부터 보면된다. 다른 수도 마찬가지이다.
만든 체를 사용해서 수를 입력받고 2부터 소수이기 때문에
2부터 입력받은 수에서 뺀다. 그랬을 때, 나온 수를 체에넣어 소수면 두 소수의 합이므로 둘을 저장한다.
이 과정을 반복하며 두 수의 차가 더 작은 수를 출력한다.
문제해결
> 가능한 최대 수 10000으로 체를만든다.
0과 1은 소수가 아니므로 처리해주고 2부터 각각의 배수들을 따진다.
> i가 N의 제곱수를 넘어가면 어차피 반복되므로 i*i까지로 범위를 줄여주고 배수도 전 반복에서 했기 때문에 j = i*i부터 배수를찾아준다.
> 각 배수들에 false를 처리하고나면 체에 소수만 true상태로남는다.
> 10000보다 작은 가장큰 소수는 9973이고 가장 작은 소수는 2이므로 두 수의 차가 젤 커지므로 두 수가 9973, 2 일 때를 피해 두수의 9974,2로 두 수의 차이인 9972를 최악으로 준다.
> 2부터 입력받은 수의 절반까지(절반넘어가면 반복되니까) 소수인지 판별해보고 소수면 n에서 그 수를 뺀수도 소수인지 확인한다.
> 둘다 소수라면 두 수를 가지고 전에 저장 됐었던 수의 차와 비교한다. 문제에서 더 작은 차를 가진 쌍을 출력하라고 했기 때문이다.
> 더 작은 쌍을 찾아 이를 저장하고 차이를 갱신해 다음 결과를 탐색한다.
> 최종적으로 다 찾으면 두 수를 작은 것 부터 출력하기 위해 정렬하고 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n;
int Max = 10000;
vector<bool> prime(Max+1, true);
void Sieve(int N)
{
prime[0] = false;
prime[1] = false;
for (int i = 2; i * i <= N; i++) //제곱수 넘어가면 어차피 중복
{
if (prime[i])
{
for (int j = i * i; j <= N; j += i)
{
prime[j] = false;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
Sieve(Max);
vector<int> rst(2);
while (T--)
{
cin >> n;
int Min = 9972;
for (int i = 2; i*2 <= n; i++)
{
if (prime[i])
{
if (prime[n - i])
{
int a = i;
int b = n - i;
if (abs(a - b) < Min)
{
Min = abs(a - b);
rst[0] = a;
rst[1] = b;
}
}
}
}
sort(rst.begin(), rst.end());
cout << rst[0] << " " << rst[1] << '\n';
}
}
후기
오랜만에 체 문제 푸니까 체 구현이 모호해졌다. 체 부분을 다시 제대로 알아보자.
