문제 출처

1. 문제설명

  • 두 끈을 이어붙이고, 그 끈을 다시 길이가 소수인 두 개의 끈으로 나눌 수 있는가?



2. 알고리즘 설계

  • 이 문제는 골드바흐의 추측과 밀접한 관계가 있다.
    • 이 추측에 의하면 4보다 큰 홀수는 두 홀수의 짝수 조합으로 나눌 수 있다.
      • 즉, 두 수의 합이 4보다 작으면 절대 불가능하다.
    • 4보다 큰 짝수 중에 소수는 없을까?



3. 로직

  • 4보다 큰 짝수 소수인지 체크하는 방법
    • 소수 중에 짝수는 2 뿐이다.
    • 다시 말해서,
      • 어떤 수에서 2를 뺀 다음,
      • 이 수가 소수로 나눠지지 않는다면?
      • 해당 숫자는 소수이다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> v;
const int SZ = 2000001;
bool arr[SZ];

void eratos() {
	arr[1] = true;

	for (int i = 2; i * i < SZ; i++) {
		if (arr[i]) continue;

		for (int j = i * i; j < SZ; j += i)
			arr[j] = true;
	}

	for (int i = 2; i < SZ; i++)
		if (!arr[i])
			v.push_back((ll)i);
}

bool is_prime(ll num) {
	bool ret = true;
	for (ll cur : v) {
		if (num <= cur) break;
		if (num % cur == 0) {
			ret = false;
			break;
		}
	}
	return ret;
}

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

	eratos();

	int TC; cin >> TC;
	while (TC--) {
		ll a, b, s; cin >> a >> b;
		s = a + b;

		if (s <= 3) cout << "NO";
		else if (s % 2 == 0) cout << "YES";
		else {
			if (is_prime(s - 2)) cout << "YES";
			else cout << "NO";
		}
		cout << '\n';
	}

	return 0;
}



5. 주의!

  • 골드바흐의 추측은,
    • 아주 큰 범위의 수까지는 해당 이론이 적용된다고 한다.
  • $2*10^2$ 까지는 적용이 되지 않는다.
    • 따라서, sqrt($2*10^2$)까지의 소수만 계산한다.