골드바흐의 추측
코드
#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만
까지 모든 수
를 에라토스테네스의 채
로 구한 뒤 소수로 나누어지는 수는 소수라는 것을 이용해서 소수인지 판별
하면 시간안에 수행이 가능