题解 P1304 【哥德巴赫猜想】

发表于 更新于 阅读次数： Waline： 阅读次数：
P1304 【哥德巴赫猜想】题解。

这题其实很简单。

首先，筛法筛一遍，打个bool质数表；

然后，读入n，i从4暴力到n！’-‘!^=^!

输出！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>//标准输入输出库
int n,i=4;//直接定好
bool s[10000]={1,1};//0和1啥都不是，定1！
//全局数组初值全为0
inline void a(){//不要在意函数名，这只是个筛法函数
    for (int j=2;j<10000;j++)//暴力！汗！
    for (int k=j*2;k<10000;k+=j)//k=j*2省一个判断，每次+j，保证是j的倍数
    s[k]=1;//既然是j的倍数，那一定是合数，标记！
}
int main(void){
    scanf ("%d",&n);
    a();//预处理
    for (;i<=n;i+=2){//疯狂的暴力！i+=2保证是偶数
        int j=2;//继续暴力
        for (;s[j]||s[i-j];j++);//s[j]||s[i-j]两个都不能是合数，如果是，继续循环
//合数为1，质数为0
        printf ("%d=%d+%d\n",i,j,i-j);//输出！
    }
}
//话说：暴力出奇迹，0msAC！