素数的一般判断方式 3+1种

素数：又叫质数，只能被1和本身整除的数。

在介绍c++方式前：先看一下素数的一些性质（来源百度百科），有些题目可能会用到

数目计算
尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。
1、在一个大于1的数a和它的2倍之间（即区间(a, 2a]中）必存在至少一个素数。
2、存在任意长度的素数等差数列。
3、一个偶数可以写成两个合数之和，其中每一个合数都最多只有9个质因数。（挪威数学家布朗，1920年）
4、一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界。（瑞尼，1948年）
5、一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 （1 + 5）（中国潘承洞，1968年）
6、一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 （1 + 2） [2]  

性质
质数具有许多独特的性质：
（1）质数p的约数只有两个：1和p。
（2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
（3）质数的个数是无限的。
（4）质数的公式是不减函数。//额。。感觉可以忽视这个
（5）若n为正整数，在n^2到(n+1)^2之间至少有一个质数。
（6）若n为大于或等于2的正整数，在n到n!之间至少有一个质数。
（7）若质数p为不超过n(n>=4)的最大质数，则p>(n/2) 。
（8）所有大于10的质数中，个位数只有1,3,7,9。

哥德巴赫猜想：每个大于4的偶数都可以写成两个奇素数的和。

下面给出3种方式：注意在剪枝i*j的时候别超出自己定义的范围（int型）

顺便提一下测试大素数的Miller_Rabin算法，有兴趣可以看看。

第一种：埃式筛法 时间复杂度O(n*log long n);总的来说就是2是素数，那么2的整数倍（4，6，8，10......）就不是素数；

void as_pri(){
	memset(as,true,sizeof as);
	as[0] = as[1] = 0;
	for(int i = 2;i<maxn;i++){
		if(as[i]){
			for(int j=i;j*i<maxn;j++){
				as[j*i]=0;
			}
		}
	}
}//可以得到bool类型的as数组；

第二种：欧拉筛法

时间复杂度接近O(n)，原理 任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去。

值得一提的是剪枝的一个条件if(i%ol_sum[j]==0) break;

i是ol_sum[j]的整数倍时（i %ol_sum[j] == 0），i*ol_sum[j]肯定被筛过，跳出循环。

      因为i可以看做ol_sum[j]*某个数， i*ol_sum[j+1]就可以看做 ol_sum[j]*某个数*ol_sum[j+1] 。而 ol_sum[j] 必定小于 ol_sum[j+1]，
所以 i*ol_sum[j+1] 必定已经被 ol_sum[j]*某个数 筛掉，就不用再做了重复判断了，比如i=4时候，3*4=12就可以不用判断，4可以成为2*2，即在后面2*6的时候会判断。

      同时我们可以发现在满足程序里的两个条件的时候，ol_sum[j]必定是ol_sum[j]*i的最小质因子。这个性质在某些题里可以用到。

void ol_pri(){
	memset(ol,true,sizeof ol);
	ol[0] = ol[1] = 0;
	int num=0;
	for(int i=2;i<maxn;i++){
		if(ol[i]) ol_sum[num++] = i;
		for(int j=0;j<num;j++){
			if(i*ol_sum[j]>maxn) break;//注意别i*ol_sum[j]可能会超int 
			ol[i*ol_sum[j]] = 0;
			if(i % ol_sum[j]==0) break;//关键 
		}
	}
}

第三种：6倍数判断法

这种方法并不适用于判断区间素数个数，而是针对特定比较大的数，不用从头开始判断，

原理：素数只可能出现在6的倍数附近。

因为：

6的倍数以外的数是什么？6的倍数就是6k，6k附近的数，6k-3,6k-2,6k-1,6k,6k+1,6k+2,6k+3,那么不在6k左右的几个数是
6k-3,6k-2,6k+2,6k+3,第一个和最后一个数是可以整除3，另两个数是可以整除2的，所以他们肯定不是素数。
所以只有6的倍数附近的两个数才有可能是质数。

为什么说可能是质数的，我举个反例，25,35,49。。。

那具体是什么时候才有可能是非质数呢？观察一下 25((6-1)*(6-1)),35((6-1)*(6+1)),49((6+1)*(6+1))，...
为什么呢？计算一下，(6k±1)(6p±1)=36kp±6p±6k±1,观看右边式子的36kp±6p±6k是6的倍数，所以他们的乘积一定是6的倍数附近的数（转自：https://blog.csdn.net/tianwei0822/article/details/78309453）；

bool pri_6(long long x){ //6倍数判素数 
    if(x==1 || x==0) return 0;
	if(x==2 || x==3) return 1;//
	if(x%6!=1 && x%6!=5) return 0;
	else{
		for(long long i=5;i<=sqrt(x);i++){
			if(x%i==0 ||x%(i+2)==0){
				return 0;
				break;
			}
		}
		return 1;
	} 
}

以上

---

测试代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
bool as[maxn],ol[maxn];
int as_sum[maxn],ol_sum[maxn];
void as_pri(){
	memset(as,true,sizeof as);
	as[0] = as[1] = 0;
	for(int i = 2;i<maxn;i++){
		if(as[i]){
			for(int j=i;j*i<maxn;j++){
				as[j*i]=0;
			}
		}
	}
/********************************************/
	int num=0;
	for(int i=2;i<maxn;i++)
	if(as[i])
	as_sum[num++]= i;
	
	for(int i=0;i<num;i++)
	cout<<as_sum[i]<<" ";
	cout<<endl;	
}
void ol_pri(){
	memset(ol,true,sizeof ol);
	ol[0] = ol[1] = 0;
	int num=0;
	for(int i=2;i<maxn;i++){
		if(ol[i]) ol_sum[num++] = i;
		for(int j=0;j<num;j++){
			if(i*ol_sum[j]>maxn) break;//注意别i*ol_sum[j]可能会超int 
			ol[i*ol_sum[j]] = 0;
			if(i % ol_sum[j]==0) break;//关键 
		}
	}
/***************************************************/
     for(int i=0;i<num;i++)
     cout<<ol_sum[i]<<" ";
     cout<<endl;
}
bool pri_6(long long x){ //6倍数判素数 
    if(x==1 || x==0) return 0;
	if(x==2 || x==3) return 1;//
	if(x%6!=1 && x%6!=5) return 0;
	else{
		for(long long i=5;i<=sqrt(x);i++){
			if(x%i==0 ||x%(i+2)==0){
				return 0;
				break;
			}
		}
		return 1;
	} 
}
int main(){
	as_pri();/*2 3 5 7 11 13 17 19 23 29 31 37 41 43 47*/
	ol_pri();/*2 3 5 7 11 13 17 19 23 29 31 37 41 43 47*/
	for(long long i=0;i<50;i++) 
	if(pri_6(i) ) printf("%lld%c",i,i==49?'\n':' '); 
	return 0;
}