判断是否为素数，一些优化方式

素数判断是acm及各种比赛中频繁出现的内容，也是最基础的，所以一定要完全掌握，下面就介绍几种常用的素数判断的优化方法。

1.(1)先说最简单的吧，复杂度o(n),也是最容易想到的

int flag=1;
for(int i=2;i<n;i++){
    if(n%i==0){
        flag=0;//如果flag==0则说明n是非素数
        break;
    }
}

(2)对于一般题目来说往往会超时的，所以可以将其复杂度降至o(sqrt(n))

for(int i=2;i*i<=n;i++){
    if(n%i==0){
        flag=0;
        break;
    }
}

(3还有一种更高级优化，可以将其复杂度降至o(sqrt(n)/3),首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；

证明：令x≥1，将大于等于5的自然数表示如下：

··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···

可以看到，不和6的倍数相邻的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个，时间复杂度O(sqrt(n)/3)。

在(2)(3)(4)中，都是一个剪枝的思想，(3)中裁剪了不必要的偶数，(4)中裁剪了不和6

的倍数相邻的数，虽然都没有降低时间复杂度的阶数，但都一定程度上加快了判断的速度。

if(n%6!=1&&n%6!=5)
		 flag=0;
for(int i=5;i*i<=n;i+=6)
{
	if(n%i==0||n%(i+2)==0)
	{
		flag=0;break;
	}
}

2.再说下打表法吧，就是你先开一个bool型数组(int型，也行，不过bool稍微快一点，数组大小须是<=所求最大数的大小)，这个缺点就是数据最大不能超过数组的最大范围(一般在1e8以内) 复杂度o(nlogn)

void dabiao()
{
	memset(vis,false,sizeof(vis));//先初始化为false，不是素数的标为true
    vis[0]=vis[1]=true;
	for(int i=2;i*i<=n;i++)
	{
		if(!vis[i])
		{
			for(int j=i*i;j<=n;j+=i)
				vis[j]=true;//素数(除了本身)它的所有倍数即为非素数，然后把他的倍数全标记为true
		}
	}	
}

新手上路不喜勿喷，后续如有发现错误，会及时修正的。