素数判断的两个方法

素数判断的两个方法

法1：最为普通的方法从1遍历到sqrt(n)，上核心代码

bool ss(int n){
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0) return 0;
	return 1;
}

法2：优化方法：
一个数是素数(n>3)的必要条件是
N一定可以写成6k+1或6k-1

N=2或3时特判一下,由必要条件可知:
如果N不在6的倍数旁边, 一定不是素数.
然后从5=6-1开始遍历,
6k-1 6k 6k+1 6k+2 6k+3 6k+4 6k-1 6(k+1) 6(k+1)+1
从上面数组可看出, 6k,6k+2,6k+4,含因数2肯定不是素数,6k+3 含因数3也不是,所以只用看6k+1,6k-1，如果N的因数含有6k+1或6k-1肯定不是素数因为(除了1和本身还有一个因子)
所以这些情况都不是的时候 该数肯定为素数
下面上核心代码。

bool ss(int n){
	if(n==2||n==3) return 1;
	if(n%6!=1||n%6!=5) return 0;
	for(int i=5;i<=sqrt(n);i+=6)
		if(n%i==0||n%(i+2)==0)
			return 0;  
	return 1;	
}