골드바흐의 추측

코드

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
int N;
bool arr[1000001];
bool isPrime(int n){
    if(n == 1) return false;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i == 0) return false;
    return true;
}
vector<int> n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(true)
    {
        cin >> N;
        if(N == 0) break;
        int a = n[0];
        int idx = 0;
        for(int i=2;i<=N/2;i++)
        {
            int tmp = N-i;
            if(isPrime(i) and isPrime(tmp))
            {
                cout <<N << " = "<< i <<" + "<< tmp << '\n';
                goto stop;
            }
            idx++;
        }
        cout << "Goldbach's conjecture is wrong." << '\n';
        stop:;
    }
    return 0;
}

• 정리
  • 소수중 2를 제외한 모든 수는 홀수
  • 모든 4이상의 짝수인 정수는 두 소수의 합으로 나타낼 수 있다
    (적당히 큰 수에서 증명 완료)

환상의 짝궁

• 풀이 방법 2가지
  • O(logN)로 소수판별 가능한 밀러-라빈 소수판별법 이용하는 방법
  • 골드바흐의 추측 + 에라토스테네스의 채 이용 (우리가 사용할 방법!)

코드

#include <cstdio>
#include <vector>
#include <iostream>
#include <cmath>
#define MM 2000001
using namespace std;
typedef long long ll;
using namespace std;
vector <int> v;
char arr[MM];

bool isPrime(ll a){
	for(int i = 0; i < (int)v.size() && (ll)v[i] * v[i] <= a; i++)
		if(a % v[i] == 0) return false;
	return true;
}

int main() {
	int T;
	cin >> T;

    /* 에라토스테네스의 채 */
	arr[1] = 1;
	for(int i = 2; i * i < MM; i++) {
		if (!arr[i])
			for(int j = i * i; j < MM; j += i)
				arr[j]++;
	}
	for(int i = 2; i < MM; i++)
		if(!arr[i]) v.push_back(i);

	ll a, b;
	while (T--) {
		cin >> a >> b;
		a += b;

		if (a < 4) { cout << "NO\n"; continue; }
		if (a % 2 == 0) { cout << "YES\n"; continue; }
		a -= 2;

		if (isPrime(a)) cout << "YES\n";
		else cout << "NO\n";
	}
}

• 이해
  • 골브바흐의 추측에 따라서 4이상의 짝수는 2개의 소수의 합으로 나타낼 수 있기 때문에 우리는 두 수의 합이 홀수 인 경우만 처리해주면 된다.
  • 그리고, 두 수의 합이 홀수인 경우는 짝수 + 홀수 인데, 소수중 짝수는 2밖에 없으므로 S = 2+(S-2) 로 소수를 나타낼수 있으니 결과적으로 S-2가 소수인지 판별하는 문제가 된다
  • 입력의 범위로 합이 최대 4조(4*10^12)가 나오므로 sqrt(4조) = 200만 까지 모든 수를 에라토스테네스의 채로 구한 뒤 소수로 나누어지는 수는 소수라는 것을 이용해서 소수인지 판별하면 시간안에 수행이 가능

• 참고
  https://m.blog.naver.com/PostView.nhn?blogId=rdd573&logNo=221270230610&proxyReferer=https:%2F%2Fwww.google.com%2F