Goldbach's Conjecture

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 940 字

多组数据，每组一个偶数n，拆成两个奇质数之和

一本通
练习

正文

/*
原题：T1622「一本通 6.2 练习 3」Goldbach's Conjecture（POJ 2262）
题意：多组数据，每组一个偶数 n（6≤n≤1e6），拆成两个奇质数之和 n=a+b，有多组时取 b-a 最大（即 a 最小）；读到 0 结束。
思路：线性筛出 1e6 内质数。对每个 n 从小往大枚举奇质数 a（从 3 起，步长 2），若 a 与 n-a 均为质数即输出并停止。
b-a 最大等价于 a 最小，故取首个满足的 a 即可。
复杂度：时间 O(数据组数·√n)，空间 O(1e6)
易错点：1) 输入以 0 结束；2) a 从奇质数 3 起（2 偶，n-a 也为偶非质数）；
3) 输出格式必须带空格：n = a + b，写成 n=a+b 会格式错误。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX=1000000;
vector<bool> isp(MAX+1,true);
void sieve(){
    isp[0]=isp[1]=false;
    for(int i=2;i*i<=MAX;i++){
        if(isp[i]){
            for(int j=i*i;j<=MAX;j+=i){
                isp[j]=false;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve();
    int n;
    while(cin>>n && n!=0){
        for(int a=3;a<=n/2;a+=2){
            if(isp[a] && isp[n-a]){
                cout<<n<<" = "<<a<<" + "<<(n-a)<<"\n";
                break;
            }
        }
    }
    return 0;
}

Goldbach's Conjecture

正文

一本通·提高篇的其它内容