哥德巴赫猜想

作者：追风剑情发布于：2015-1-4 21:53 分类：Algorithms

任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和。

数值验证: C语言

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

// Eratosthenes算法
// 将指定范围中的素数都筛选出来保存到一个数组中。
int CreatePrime(int n, int prime[])
{
	int i,j;
	for(i=2; i<=n; i++)//初始化数组
		prime[i] = 1;//标志为1表示对应的数是质数
	prime[0]=prime[1]=0;
	for(i=2; i*i<=n; i++)//循环处理前i个
	{
		if(prime[i] == 1)//若为素数标记
		{
			for(j=2*i; j<=n; j++)//筛去合数
			{
				if(j%i==0)//能被整除
					prime[j]=0;//不是素数
			}
		}
	}
}

int main()
{
	int n,i,j,flag;
	int *prime;
	printf("哥德巴赫猜想验证\n");
	printf("输入一个要验证的最大数n(n>=6:)");
	scanf("%d", &n);
	if(n < 6)//判断输入数据是否合法
	{
		printf("数据输入错误!\n");
		return 0;
	}
	if(!(prime=(int *)malloc(sizeof(int)*n)))
	{
		printf("分配内存失败!\n");
		getch();
		return 0;
	}
	CreatePrime(n, prime);//生成素数数组
	for(i=6; i<=n; i+=2)//从6开始，循环验证各偶数
	{
		flag = 1;
		for(j=2; j<=i/2; j++)
		{
			//判断组成每个数的两个加数
			//若一个加数是偶数，不判断素数
			if(j%2==0 || ((i-j)%2==0)) continue;
			//若两个加数都是素数
			if(prime[j]==1 && prime[i-j]==1)
			{
				printf("%d=%d+%d\n", i, j, i-j);//输出素数
				flag = 0;//清除标志
				break;
			}
		}
		if(1==flag)
			printf("找到一个不符合要求的偶数:%d\n", i);
	}

	getch();
	return 0;
}

运行结果: 找1000000以内的素数