哥德巴赫猜想：偶数拆分质数之和

哥德巴赫猜想：偶数拆分质数之和

1742年6月7日哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想： a. 任何一个大于6的偶数都可以表示成两个素数之和。 b. 任何一个大于9的奇数都可以表示成三个素数之和。 这就是哥德巴赫猜想。

现在请输出一个大于等于4的偶数都可以拆分为两个素数之和。

输入

一个整数n( 4 <= n <= 200 )

输出

将小于等于n的偶数拆分为2个质数之和，列出所有方案！注意：（3，5）和（5，3）被认为是同一种方案

样例输入

10

样例输出

4=2+2
6=3+3
8=3+5
10=3+7
10=5+5

C++ 代码

#include<bits/stdc++.h>
using namespace std;
bool prim[5000001];
int prime[5000001];
void pre(int n){
    memset(prim, true, sizeof(prim));
    int cnt=0;
    for (int i=2;i<=n;i++){
        if (prim[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt&&prime[j]*i<=n;j++){
            prim[prime[j]*i]=false;
            if (i%prime[j]==0) break;
        }    
    }
}
int main(){
    int n;
    cin>>n;
    if (n<6) return 0;
    pre(n);
    for (int i=4;i<=n;i+=2){
        for (int j=1;j<=n;j++){
            if (prime[j]>=i) break;
            if (prim[i-prime[j]]){
                cout<<i<<'='<<prime[j]<<'+'<<i-prime[j]<<endl;
                break;
            }
        }
    }
    return 0;
}