[백준] 9020번 - 골드바흐의 추측
문제
골드바흐의 추측은 간단히 말해 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 다만 문제에서는 다양한 답들 중, 두 소수의 제일 작은 답을 출력하라하였으므로, 주어진 수의 절반에서 시작해서 소수를 찾으면 되는 매우 쉬운 문제이다. 범위는 10,000까지이기에 에라토스테네스의 체를 이용하여 주어진 범위까지의 소수를 모두 찾은 후 연산하면 편하다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
int main(void) | |
{ | |
bool prime[10001]; | |
for(int i=2; i<=10000; i++) | |
prime[i] = 1; | |
for(int i=2; i<=10000; i++) | |
{ | |
if(prime[i]) | |
for(int j=i*2; j<=10000; j+=i) | |
prime[j] = 0; | |
} | |
int t; | |
cin >> t; | |
for(int i=0; i<t; i++) | |
{ | |
int n; | |
cin >> n; | |
int a = n/2, b= n/2; | |
while(1) | |
{ | |
if(prime[a] && prime[b]) | |
{ | |
cout << a << " " << b << "\n"; | |
break; | |
} | |
a--, b++; | |
} | |
} | |
return 0; | |
} |