poj ——2262水题素数问题

题意：一个偶数能不能表示为两个奇质数a跟b的和，如果能的话由于这个偶数可能可以表示为多个奇质数对的和，输出时只选取b-a最大的那对奇质数

 

选题原因：本题难度适中，是关于素数的问题，涉及的是素数表的构造，另外，本题很容易超时，要注意处理方法。

 

思路：以空间换时间，利用筛选法求素数

此题用筛选法构造素数表：基本思路如下：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛法”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

筛选法代码如下：

 

 

<!--EndFragment-->

void oddp()
{
	int i,j;
	for (i=2;i<Max;i++)
		a[i]=1;
	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;
		}
	}
	
}

 本题代码如下：
 

#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[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),有一个能除尽就不是素数，否则是素数。

时间复杂度：O(sqrt(n))

2、素数判断法：

这种方法是对上面方法的改进，上面方法是对2-sqrt(n)之间的数进行判断是否能除尽，而因为有如下算术基本定理，可以减少判断量。

算术基本定理：又称为素数的唯一分解定理，即：每个大于1的自然数均可写为素数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如:6936 = 2^3×3×17^2，1200 = 2^4×3×5^2。

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

3、筛选法

这种方法可以找出一定范围内的所有的素数。

思路是，要求10000以内的所有素数，把1-10000这些数都列出来，1不是素数，划掉；2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的所有倍数；直到所有幸存的数的倍数都被坏掉为止。要找出10000以为的所有的素数，则需要一个大小为10000的数组,将其所有元素设置为未标记首先把1设置为标记，从2开始，标记所有是它倍数的数，然后对下一个没有标记的数进行标记它的倍数。当标记完成后，所有未标记的数即为素数。

int prime100[] =   //100以内的素数

{

  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,

};

 

第一种方法：试除法

int is_prime1(int n)

{

    if(n % 2 == 0)

        return 0;

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

        if(n % i == 0)

            return 0;

    return 1;

}

 

第二种方法：素数判断法

若判断10000以内的数，需要知道100以内的所有素数

int is_prime2(int n)

{

    int i;

    for(i=0;i<25;i++)

        if(n % prime100[i] == 0)

            return 0;

    return 1;

}

 

第三种方法：筛选法，打素数表，然后判断(见本题)。

<!--EndFragment-->