[C/C++ 백준 15711번] 환상의 짝꿍 (Gold 4)

www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

기본 전략은, 골드 바흐의 추측을 사용하는 것. 문제의 범위 정도에 대해서는 모든 짝수가 두 소수의 합으로 표현된다고 알려져 있으므로 해당 사실을 이용하자.

 

문제가 되는 것은 홀수일 때인데, 2를 제외하고는 모든 소수가 홀수이므로 반드시 2와 다른 소수의 합으로 이루어져있어야 한다. 그러니까  A+B-2가 소수인지 아닌지 판단만 하면 된다. A+B의 범위가 4 × 10^12이므로, 해당 수의 제곱근은 2 × 10^6까지 에라토스테네스의 체를 만들고 소수를 모두 찾은 뒤, 해당 수보다 같거나 작을 경우 바로 판단해주고 아닐 경우 2 × 10^6까지 소수들에 대해 모두 나눠본 이후 판단해주자.

 

이상하게 찜찜한 문제,,

 

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
bool chae[2000001];
vector <int> prime;
bool OK(long long int N){
	if(N<=3)
		return false;
	else if(N%2==0)
		return true;
	else{
		N -= 2;
		if(N<=2000000){
			if(!chae[N])
				return true;
			else
				return false;
		}
		else{
			for(int i=0; i<prime.size(); i++){
				if(N%prime[i]==0)
					return false;
			}
			return true;
		}
	}
}
int main(void){
	//1 ~ sqrt(sqrt(2*10^6)) 소수 평가부터 해보자..
	chae[0] = chae[1] = true;
	for(int i=2; i<=2000000; i++){
		if(!chae[i]){
			prime.push_back(i);
			for(int j = i+i; j<=2000000; j+=i){
				chae[j] = true;
			}
		}
	}
	int T;
	long long int A, B;
	scanf("%d", &T);
	for(int i=0; i<T; i++){
		scanf("%lld %lld", &A, &B);
		if(OK(A+B))
			printf("YES\n");
		else
			printf("NO\n");
	}
}