이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 109 번째 글 입니다.
목차
실버1 : 수학 문제이다.
생각
소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다. 이 때, 시간제한 때문에 구한 소수를 담아두는 것이 좋다.
Code
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAX 10000
using namespace std;
bool isPrime[MAX+1];
void SeiveofEratosThenes(){
fill(isPrime+2, isPrime+MAX+1, true);
for (int i = 2; i*i <= MAX; i++) {
if (isPrime[i] == false) continue;
for (int j = i*i; j <= MAX; j+=i) {
isPrime[j] = false;
}
}
}
void solve(int N){
vector<int> prime;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) prime.push_back(i);
}
int size = int(prime.size());
int a = -100000, b = 100000;
for (int i = 0; i <= size; i++) {
for (int j = i; j <= size; j++) {
if (prime[i]+prime[j] == N) {
if (prime[j]-prime[i] < b-a) {
a = prime[i]; b = prime[j];
}
}
}
}
cout << a << " " << b << '\n';
}
int main(){
SeiveofEratosThenes();
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int N;
cin >> N;
solve(N);
}
return 0;
}