2262.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"algorithm"
using namespace std;

bool sign[1000001];
int prime[1000001],size;

int main()
{
	int n,j,i;
	int const *p;
	
	for(i=2;i<=1000000;i++)
		sign[i]=1;
	
	size=0;

	for(i=2;i<=1000000;i++)
	if(sign[i])
	{
		if(i!=2)prime[size++]=i;
		for(j=2;j*i<=1000000;j++)
			sign[i*j]=0;
	}
	sign[2]=0;

	while(1)
	{
		cin>>n;
		if(n==0)break;
		p=prime;
		for(;!sign[n-*p];p++)
			;
		cout<<n<<" = "<<*p<<" + "<<n-*p<<endl;
	}
	return 0;
}