백준 9020번 문제(골드바흐의 추측) C++로 풀기
문제 요약
주어진 n의 골드바흐 파티션을 출력한다.
코드
#include <iostream>
using namespace std;
const int range=10001;
int main()
{
int nums[range]={0,};
for(int j=2;j<range;j++)
{
nums[j]=j;
}
for(int k=2;k<range;k++) // 에라토스테네스의 체
{
if(nums[k]==0) continue;
for(int l=2*k;l<range;l+=k)
{
nums[l]=0;
}
}
int t;
scanf("%d",&t);
while(t!=0)
{
int n;
scanf("%d",&n);
int g1,g2; // 골드바흐 파티션
for(int h=n/2;h<n;h++)
{
if(nums[h]!=0 && nums[n-h]!=0) // 파티션끼리 차이가 적게 하기 위함
{
g2=nums[h];
g1=n-g2;
break;
}
}
printf("%d %d\n",g1,g2);
t--;
}
}
풀이
소수를 문제 범위까지 만들고, 최소 차이가 나는 골드바흐 파티션을 출력한다.
파티션끼리 차이가 최소로 나기 위해, 입력받은 수 n을 절반으로 나눠 n/2부터 n까지에서 n/2와 가장 가까운 소수를 찾았다.
주의점
파티션끼리 차이가 최대한 적게 나야한다.
Author And Source
이 문제에 관하여(백준 9020번 문제(골드바흐의 추측) C++로 풀기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@doctorson11/백준-9020번-문제골드바흐의-추측-C로-풀기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)