백준 15711 환상의 짝꿍

문제링크

https://www.acmicpc.net/problem/15711

문제

풀이

S = A+B 에서 S를 두 소수의 합으로 나타낼 수 있는지 판별하는 문제이다.

1. S가 짝수인 경우 :
   1-1 S가 2라면 두 소수의 합으로 나타낼 수 없다.

   1-2 S가 2가 아니라면 골드바흐의 추측에 의해 두 소수의
   합으로 나타낼 수 있다.
   
   

2. S가 홀수인 경우 :

   S가 홀수인 경우 두 소수의 합으로 나타낼 수 있는 경우의 수는 2+소수인 경우 뿐이다.
   따라서 S-2 가 소수라면 S는 두 소수의 합으로 나타낼 수 있다.

   에라토스테네스의 체 알고리즘을 이용해 A+B의 최대 범위 4*10^12 의 제곱근인 2000000 까지의 소수를 미리 구해놓는다.

   S <= 2000000 이라면 isprime 배열의 값에 따라 소수인지 판별이 가능하다.
   S > 2000000 인 경우 벡터에 담아놓은 소수들로 나누어 떨어지지 않는다면 소수이다.
   (모든 수는 소수를 약수로 가지고 있으므로)

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int PN = 2000000;
bool isprime[PN + 5];
vector<int> prime;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (ll i = 2; i <= PN; i++) isprime[i] = true;
	for (ll i = 2; i <= PN; i++)
		if (isprime[i])
			for (ll j = i * i; j <= PN; j += i) {
				isprime[j] = false;
			}

	for (int i = 2; i <= PN; i++) {
		if (isprime[i]) prime.push_back(i);
	}

	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		ll a, b;
		cin >> a >> b;
		ll S = a + b;
		if (S % 2 == 0) {
			if (S == 2) {
				cout << "NO\n";
			}
			else {
				cout << "YES\n";
			}
		}
		else {
			bool check = true;
			S -= 2;
			if (S <= PN) {
				if (isprime[S]) cout << "YES\n";
				else cout << "NO\n";
			}
			else {
				for (int j = 0; j < prime.size(); j++) {
					if (S % prime[j]==0) {
						check = false;
						break;
					}
				}
				if (check) cout << "YES\n";
				else cout << "NO\n";
			}
		}
	}
}

후기

• 사용된 알고리즘
  
  1. 골드바흐의 추측

  2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다

  2. 에라토스테네스의 체
  

       Reference : 에라토스테네스의 체 (Wikipedia)
       Reference : 에라토스테네스의 체2