哥德巴赫猜想

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 655 字

把 4..N 的每个偶数拆成两质数之和（首加数最小）

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1439）
// 题意：对 4..N 的每个偶数，输出一种拆成两个质数之和的方案，要求第一个加数尽量小。
// 思路：对每个偶数 e，从 2 起找最小的质数 p 使 e-p 也是质数，输出 e=p+(e-p)。
// 复杂度：O(N^2 / log N)。
// 易错点：要“最小的第一个加数”；用试除法判质数即可。
#include <iostream>
using namespace std;
bool isprime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
    return true;
}
int main(){
    int N;
    cin >> N;
    for(int e = 4; e <= N; e += 2){
        for(int p = 2; p <= e / 2; p++){
            if(isprime(p) && isprime(e - p)){
                cout << e << "=" << p << "+" << e - p << endl;
                break;
            }
        }
    }
    return 0;
}

哥德巴赫猜想

正文

洛谷·深入浅出的其它内容