백준 BOJ 15711 - 환상의 짝꿍

소수판별 문제의 살짝 심화된 버전.

www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

생각해볼수 있는 수학적 개념 / 코너케이스로는 크게 세가지정도가 있다.

1.  3 이하의 수가 들어오는 경우에는 절대로 소수의 합으로 표현할 수 없다. 반드시 NO를 출력해주자.

2.  4 이상의 모든 짝수는 골드바흐의 추측에 따라 두 소수의 합으로 표현할수있음이 증명된다.

3.  a와 b는 int범위를 벗어난다. 반드시 longlongint를 쓰자.

 

모든 짝수는 그냥 YES를 출력하고, 홀수에 대해서

처음엔 그냥 루트 시간복잡도를 가지는 소수판별함수를 짜서 별다른 저장 없이 바로 처리했는데,

시간초과가 났다.

 

그래서 모든 합성수는 소수와 그 곱으로 표현할 수 있다는 것을 이용해서,

루트 a+b까지의 모든 소수를 미리 구하고, 나누어보는방법을 사용했다.

모든 소수를 미리 구하는 과정에서 에라토스테네스의 체가 사용되었고,

소수의 저장은 벡터에다 해주었다.

 

#include <stdio.h>
#include <vector>

using namespace std;

typedef long long int ll;

vector<int> v; // 소수 배열 // 
ll chk[2000002] = {0}; // 아리스토테네스의 체 // 

int prime(ll k){
	for(int i=0; v[i]*v[i]<=k && i<v.size(); i++) if(k%v[i] == 0) return 0;
	return 1;
}

int main(){
	// 전처리 //
	chk[0] = chk[1] = 1;
	for(int i=2; i*i < 2000002; i++)
		if(!chk[i])
			for(int j=i*i; j < 2000002; j+=i)
				chk[j]=1;
	
	for(int i=1; i<2000002; i++)
		if(!chk[i]) 
			v.push_back(i);
	// 전처리 끝 //
	
	int t;
	ll a,b;
	ll tmp;
	scanf("%d", &t);
	while(t--){
		scanf("%lld %lld", &a, &b);
		tmp = a+b;
		
		if(tmp < 4)         puts("NO");  // 3 이하로는 불가능. 
		else if(tmp%2 == 0) puts("YES"); // 골드바흐의 추측.
		else printf("%s\n", prime(tmp-2)?"YES":"NO");
	}
	return 0;
}

이렇게 짜주면 빠르게 AC를 받을 수 있다.