1622：Goldbach’s Conjecture
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
原题来自：Ulm Local，题面详见：POJ 2262
哥德巴赫猜想：任何大于 44 的偶数都可以拆成两个奇素数之和。 比如：
8=3+5
20=3+17=7+13
42=5+37=11+31=13+29=19+23
你的任务是：验证小于 106 的数满足哥德巴赫猜想。
【输入】
多组数据，每组数据一个 n。
读入以 0 结束。
【输出】
对于每组数据，输出形如 n=a+b，其中 a,b 是奇素数。若有多组满足条件的 a,b，输出 b−a 最大的一组。
若无解，输出 Goldbach′s conjecture is wrong.。
【输入样例】
8
20
42
0
【输出样例】
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
【提示】
数据范围与提示：
对于全部数据，6≤n≤106 。
sol：欧拉筛筛出素数后暴力枚举
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=;
int n;
int Prim[N];
bool Bo[N];
inline void Pre_Prime()
{
int i,j;
for(i=;i<=;i++)
{
if(!Bo[i]) Prim[++*Prim]=i;
for(j=;j<=*Prim&&Prim[j]*i<=;j++)
{
Bo[Prim[j]*i]=;
if(i%Prim[j]==) break;
}
}
return;
}
int main()
{
int i;
Pre_Prime();
while(true)
{
bool Flag=;
if(!(n=read())) break;
for(i=;i<=*Prim&&Prim[i]<n;i++) if(!Bo[n-Prim[i]])
{
printf("%d = %d + %d\n",n,Prim[i],n-Prim[i]);
Flag=;
break;
}
if(!Flag)puts("Goldbach's conjecture is wrong.");
}
return ;
}
/*
input
8
20
42
0
output
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
*/