首页 > 代码库 > luogu P1304 哥德巴赫猜想
luogu P1304 哥德巴赫猜想
题目描述
输入N(N<=10000)，验证4~N所有偶数是否符合哥德巴赫猜想。
（N为偶数）。
如果一个数，例如10，则输出第一个加数相比其他解法最小的方案。如10=3+7=5+5，则10=5+5是错误答案。
输入输出格式
输入格式：
第一行N
输出格式：
4=2+2 6=3+3 …… N=x+y
输入输出样例
输入样例#1：
10
输出样例#1：
4=2+26=3+38=3+510=3+7
枚举
#include<cstdio>#include<cmath>using namespace std;int n;bool a[10006];int num_prime=0, prime[10006];void init(){ scanf("%d",&n); a[0]=a[1]=1; for(int i=2;i<=n;i++) { if(!a[i]) prime[num_prime++]=i; for(int j=0;j<num_prime&&i*prime[j]<=n;j++) { a[i*prime[j]]=1; if(!(i%prime[j])) break; } }}void solve(int x){ int i=0; while(prime[i]<x) { int tmp=x-prime[i]; if(!a[tmp]) { printf("%d=%d+%d\n",x,prime[i],tmp); return; } i++; }}int main(){ init(); for(int i=4;i<=n;i+=2) { solve(i); } return 0;}
luogu P1304 哥德巴赫猜想
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。