gedebahe.cpp

验证哥德巴赫猜想

//Example：“验证”歌德巴赫猜想
#include <iostream>
using namespace std;
#define M 10001          //定义验证范围
// 函数CreatPrimeList()：生成素数表
void CreatPrimeList(int PrimeList[])
{
	int i,j;
	//将PrimeList的各元素设置为从0开始的正整数
	for(i=0;i<M;i++)
		PrimeList[i]=i;
	//分别从表中去掉已经确定的各素数的倍数（将其置为0)
	i=2;
	while(i<M/2)
	{
		for(j=i+1;j<M;j++)
			if(PrimeList[j]!=0 && PrimeList[j]%PrimeList[i]==0)
				PrimeList[j]=0;
			//确定下一个素数的位置
			i=i+1;
			while(PrimeList[i]==0)
				i=i+1;
	}
}
//函数NextPrimeNumber():求下一个素数
int NextPrimeNumber(int p,int PrimeList[])
{
	p=p+1;
	while(PrimeList[p]==0)
	p=p+1;
	return PrimeList[p];
}
//主函数：在从4~M的范围内验证歌德巴赫猜想
int main()
{
	int PrimeList[M];  //定义存放素数表的数组
	int x,p;           //定义x:偶数， p:素数
	//建立素数表
	CreatPrimeList(PrimeList);
	//对从4~M的所有偶数验证哥德巴赫猜想
	x=4;
	while(x<M)
	{
		//检查偶数减去一个素数后的剩余部分是否仍为素数
		p=PrimeList[2];
		while(p<=x/2&&PrimeList[x-p]==0)
			p=NextPrimeNumber(p,PrimeList);
		//输出检查结果
		if(p>x/2) //找到了一个不能分解为两个素数和的偶数
		{
			cout<<"Great discovery:Goldbach is wrong!"<<endl;
			break;
		}
		else  // PrimeList[x-p]!=0,分解成功
			cout<<"The even number "<<x<<"="<<p<<"+"<<x-p<<endl;
		//检查下一个偶数
		x=x+2;
	}
	return 0;
}