欧拉筛（回顾） 11@亿万星辰 poj_2262哥德巴赫猜想

#include<cstdio>
#define MAX 1000000
int phi[MAX+10],pri[MAX+10],cnt=0;
bool f[MAX+10];
void getphi()//欧拉筛筛素数和phi值 
{
	phi[1]=1;
	for(int i=2;i<=MAX;i++)
	{
		if(!f[i]) {
			pri[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&i*pri[j]<=MAX;j++)
		{
			f[i*pri[j]]=1;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			else phi[i*pri[j]]=phi[i]*(pri[j]-1);
		}
	}
}
void solve(int n)//判断是否符合题意 
{
	int m;
	for(int i=2;i<=cnt;i++)
	{
		m=n-pri[i];
		if(phi[m]==m-1) {
			printf("%d = %d + %d\n",n,pri[i],m);
			break;
		}
	}
}
int main()
{
	char ch;
	int num,cnt=1;
	getphi();
	while((ch=getchar())<'0'||ch>'9');//消非可用字符 
	while(ch!=48)
	{
		num=ch^48;
		while((ch=getchar())>='0'&&ch<='9') num=10*num+(ch^48);//快读
		solve(num); 
		cnt++;
		while((ch=getchar())<'0'||ch>'9');
	}
	return 0;
 }