题目大意就是输入一个不小于6的合数，把它表示成两个质数的和，如果有多个，数出相差最大的一组

此题用筛选法构造素数表：基本思路如下：先把N个自然数按次序排列起来。

1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。

2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。

这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数

这种方法虽然速度比较快，空间要求比较大

#include <iostream>

#include <stdio.h>

using namespace std;

#define Max 1000000

int a[Max];

void oddp()

{

int i,j;

for (i=2;i<Max;i++)

a[i]=1;//a[i]存放i

a[0]=0,a[1]=0;

for (i=2;i<Max;i++)

{

if (a[i]==1)

{

for (j=i*2;j<Max;j+=i)

a[j]=0;

}

}

}

int main()

{

int n;

int i,flag;

oddp();

while (cin>>n&&n!=0)

{

for (flag=0,i=2;i<n;i++)

{

if (a[i]==1&&a[n-i]==1)

{

printf("%d = %d + %d\n",n,i,n-i);

flag=1;

break;

}

}

if (flag==0)

printf("Goldbach‘s conjecture is wrong.\n");

}

return 0;

}

其他关于判断素数的方法：

1、最简单的方法

用n除以2-sqrt(n),有一个能除尽就不是素数，否则是素数。

int is_prime1(int n)

{

    if(n % 2 == 0)

        return 0;

///从3开始到sqrt(n),并且步长为2

    for(int i=3;i<=sqrt((double)n);i+=2)

        if(n % i == 0)

            return 0;

    return 1;

}

2. 改进法

由算术基本定理知，任何合数都可分解为一些素数的乘积，所以判断一个数能不能被2-sqrt(n)之间的素数整除（而不是尝试所有的数）即可。但是必须知道2-sqrt(n)之间的所有素数。

3筛选法

math2262