关于素数算法总结

本文参考地址：http://www.kuqin.com/math/20071231/3269.html

http://hi.baidu.com/sulipol/blog/item/c6dd6c171eb81258f2de3270.html

判断素数：时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).

bool isprime( int num )
{
	int i ;
	int sq;
	if (num <=1) return 0;

	sq= (int)sqrt( num );
	for (i = 2 ;i <= sq ; i++ )
	{
		if ( num % i == 0 )
		{
			break ;
		}
	}
	if ( i <= sq )
		return 0;
	else
		return 1 ;
}

快速查找和输出素数 打表法

#include<stdio.h>
#include<math.h>
两种打表比较，第二种内存脚省，但是时间可能比较长一点

#define N 100000

int a[N];
int s1[100000];

int main()
{
	int i,j,k,n;

	for(i=0;i<=N;i++)//初始化表一
		a[i]=1;

	n=(int)sqrt(N);//注意n！！！
	for(i=2;i<=n;i++)//表一进行打表
	{
		for(j=i+i;j<=N;j+=i)//素数的倍数不是素数原理
			a[j]=0;
	}

	k=1;
	for(i=2;i<=N;i++)//将表一的素数存入表二，打表完成
		if(a[i])
		{
			s1[k]=i;
			k++;
		}

		for(i=1;i<k;i++)
			printf("%d\t",s1[i]);

		return 0;
}

打表法二：
/*方法运用了奇数对相关知识 证明见算法下面*/
/*1.首先素数先排除2和3的倍数*/
/*2.对6*n-1和6*n+1进行判断是否为素数。判断过程为3.*/
/*3.将当前6*n-1和6*n+1对素数表s[]中的前1~sqrt(le)+1 个数进行mod运算，都不能mod尽的为素数，并存表*/
/*重复2.和 3.的步骤直到循环结束*/
#include<stdio.h>
#include<math.h>
#define N 1000

int s[N];

int main()
{
    int i,j,ls,n;
	int a,b,sign1,sign2;

	s[1]=2;//步骤1
	s[2]=3;
	ls=2;
    for(i=6;i<N;i=i+6)//步骤2
	{
		a=i-1;
		b=i+1;
		sign1=1;
		sign2=1;
		n=(int)sqrt(ls);
		for(j=1;j<=n+1;j++)//步骤3.
		{
			if(a%s[j]==0)
			{
				sign1=0;
				break;
			}
		}

		for(j=1;j<=n+1;j++)
		{
			if(b%s[j]==0)
			{
				sign2=0;
				break;
			}
		}

		if(sign1)//素数存表
		{
			ls+=1;
			s[ls]=a;
		}
		if(sign2)
		{
			ls+=1;
			s[ls]=b;
		}

	}

    for(i=1;i<=ls;i++)
		printf(" %d\t",s[i]);
	return 0;
}

首先，说一下奇数对的概念：

中间只隔一个数字的两个素数（素数除了2之外都是奇数啦）被称为奇数对，比如17和19，29和31等等。证明奇数对之间的数字总能被6整除(假设这两个素数都大于6)。现在证明没有由三个素数组成的奇数对。

(注* 网上关于微软面试题的奇数对的概念是有误的，大概为翻译过来的错误)

方法二证明：

假设p和p+2是两个大于6的素数，则中间那个数为p+1。p+1为偶数，可以被2整除。p, p+1, p+2是三个连续的自然数，其中必然有一个能被3整除（不用证明了吧）。由于p和p+2都是大于6的素数，所以这个能被3整除的数必定是p+1。所以p+1能够被6整除。

同样，如果p是奇素数，则p, p+2, p+4之间必定有一个能够被3整除，所以不存在由三个素数组成的素数对。