AcWing 1292. 哥德巴赫猜想 (预处理、欧拉筛）
AcWing 1292. 哥德巴赫猜想 (预处理、欧拉筛）
glm233
发布于 2021-03-02 15:08:53
发布于 2021-03-02 15:08:53
代码可运行
运行总次数：0
代码可运行
哥德巴赫猜想的内容如下：
任意一个大于 44 的偶数都可以拆成两个奇素数之和。
例如：
8=3+58=3+5 20=3+17=7+1320=3+17=7+13 42=5+37=11+31=13+29=19+2342=5+37=11+31=13+29=19+23
现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。
输入格式
输入包含多组数据。
每组数据占一行，包含一个偶数 nn。
读入以 00 结束。
输出格式
对于每组数据，输出形如 n = a + b，其中 a,ba,b 是奇素数。
若有多组满足条件的 a,ba,b，输出 b−ab−a 最大的一组。
若无解，输出 Goldbach's conjecture is wrong.。
数据范围
6≤n<1066≤n<106
输入样例：
8
20
42
0输出样例：
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37思路：直接平方枚举肯定超时，我们可以先线性预处理出1e6以内的质数，然后单个枚举，相当于打表map去看另外一个是不是也是奇素数~
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,pr[N],cnt;
bool st[N];
void init(int n){
for(int i=2;i<=n;i++){
if(!st[i])pr[cnt++]=i;
for(int j=0;pr[j]*i<=n;j++){
st[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
int main(){
init(N);
while(cin>>n,n){
for(int i=0;pr[i]<n;i++){
int a=pr[i];
if(!st[n-a]){
printf("%d = %d + %d\n",n,a,n-a);
break;
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/02/23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
