C++ / 백준 / 15711 / 환상의 짝꿍

문제

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

15711번: 환상의 짝꿍

문제풀이

A+B의 최댓값은 4*10^12 이므로 구할 소수의 최댓값을 2*10^6으로 두고 했다.

A+B=2, 3일 때는 소수의 합으로 나타낼 수 없으므로 NO를 출력한다.

적당한 범위 내에선 골드바흐의 추측이 맞으므로 A+B의 값이 짝수일 경우는 YES를 출력하면 된다.

 

값이 홀수가 나오려면 홀수+짝수의 경우의 수밖에 없다.

그리고 소수 중에 짝수인 수는 2밖에 없으므로 A+B-2의 값이 소수인지만 판별하면 된다.

2,000,000까지의 수 중에서 소수를 에라토스테네스의 체를 이용하여 미리 구한다.

A+B의 값에서 2를 뺀 후 미리 구한 모든 소수를 이용하여 나눠본 후 나머지가 0인지, 0이 아닌지만 판별하면 된다.

 

 

코드

#include <iostream>
#include <vector>
#include <cmath>
using  namespace std;
#define MAX_N 2000000

vector<bool>isPrime(MAX_N + 1, true);
vector<long long>prime;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	long long T(0), A(0), B(0), C(0), idx(0), idx2(0);
	cin >> T;

	for (idx = 2; idx < sqrt(MAX_N); ++idx) {
		for (idx2 = 2; idx2 * idx < MAX_N; ++idx2) {
			isPrime[idx * idx2] = false;
		}
	}
	for (idx = 2; idx < isPrime.size(); ++idx) {
		if (isPrime[idx] == true)
			prime.push_back(idx);
	}

	while (T--) {
		cin >> A >> B;
		C = A + B;
		if (C <= 3) cout << "NO\n";
		else if (C % 2 == 0) cout << "YES\n";
		else {
			bool answer(true);
			C -= 2;
			for (idx = 0; prime[idx] <= sqrt(C); ++idx) {
				if (C % prime[idx] == 0) {
					answer = false;
					break;
				}
			}
			if (answer == true)
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}
}