15711 환상의 짝꿍 C++

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

15711번: 환상의 짝꿍

입력으로 들어오는 두 수의 합이 소수의 합으로 만들 수 있는 지 구하는 문제입니다. 처음에 밀러라빈으로 풀려는데 계속 틀렸다 그래서 에라토스테네스 체로 확실하게 풀었습니다. (아무래도테스트 케이스 중에 수도 프라임인데 합성수인게 있는 듯 하다....)

 

2,3 은 무조건 안되는 경우, 2보다 큰 짝수는 골드바흐 추측에 의해 두 소수의 합으로 표현됩니다. (아직 참인지는 모르지만 아주 큰 수까지도 성립합니다!)

그러므로 홀수일 때만 판단하면 되는데 홀수 = 홀수 + 짝수이므로 해당 합 - 2 가 소수이면 참 아니면 거짓입니다. 짝수이면서 소수인 것은 2 뿐이기 때문입니다.

 

최대 합이 4조이므로 200만까지 에라토스테네스체를 이용해 소수를 구한 다음 판별하고자 하는 수가 200만까지 소수들로 나눠봤을 때 나눠지는지 확인합니다.

 

(밀러 라빈은 정말 왜 안 되지...??? 위키 기준으로 4조 정도면 2 ~ 17까지만 a 로 잡고 판단해도 된다 그랬는데.....)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

int T;
long long A, B;
bool is_prime[2000001];
int max_num = 2000001;
vector<long long>primes;

void init()
{
	cin >> A >> B;
}

void yes()
{
	cout << "YES";
}

void no()
{
	cout << "NO";
}

void Eratos()
{
	memset(is_prime, true, sizeof(is_prime));

	for (int i = 2; i * i < max_num; i++) {
		if (is_prime[i] == true) {
			for (int j = i * i; j < max_num; j += i)
				is_prime[j] = false;
		}
	}

	for (int i = 2; i < max_num; i++) {
		if (is_prime[i] == true)
			primes.push_back((long long)i);
	}
}

bool check_prime(long long num)
{
	bool check = true;
	for (int i = 0; i < primes.size(); i++) {
		if (num <= primes[i])
			break;

		if (num % primes[i] == 0) {
			check = false;
			break;
		}
	}
	return check;
}

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

	// 골드바흐 추측이 참이라 가정하고
	// 짝수일 때는 항상 참 (2 제외)
	// 홀수 = 홀수 + 짝수
	// 결국 A+B - 2가 소수면 true 아니면 false
	
	// 밀러 라빈 쓰니까 틀렸다 그럼 (수도 프라임이지만 합성수인게 테스트 케이스에 있는 듯)
	// 에라토스테네스 체를 쓰자
	// 최대 4조니까 2백만까지만 에라토스테네스체로 구하자

	Eratos();

	cin >> T;
	while (T--) {

		init();

		long long sum = A + B;

		if (sum <= 3) // 무조건 안 됨
			no();
		else if ((sum & 1) == 0) // 2보다 큰 짝수
			yes();
		else {
			// 2보다 큰 홀수
			// 무조건 2 + 소수 꼴
			long long num = sum - 2;
			if (check_prime(num))
				yes();
			else
				no();
		}

		if (T != 0)
			cout << '\n';
	}
}