素数（质数）：大于1的自然数，只能被1和它本身整除。 简单判断
bool isprime(int n) { if(n<2) return false; for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; }打表+判断
int prime[]={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}; bool isprime(int n) { int len=sizeof(prime)/sizeof(int);//len为数组中元素个数 if(n<=prime[len-1]) { for(int i=0;i<len&&prime[i]<=n;i++) if(prime[i]==n) return true; return false; } for(int i=0;i<len;i++) if(n%prime[i]==0) return false; return true; }这样可以判断表中最大素数（97）的下一个素数（101）减1的平方（10000）以内的数是否为素数，可以扩大素数表来增大判断素数范围，可以用之后介绍的代码打表。
效率O(NlglgN) 原理
要得到自然数n以内的全部素数，必须把不大于 n√ 的所有素数的倍数剔除，剩下的就是素数。 详细步骤：当n=25时 列出2以后的所有序列： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个素数，也就是2，划掉2的倍数，序列变成： 2 3 5 7 9 11 13 15 17 19 21 23 25 下一个素数是3，将序列中3的倍数划掉，序列变成： 2 3 5 7 11 13 17 19 23 25 下一个素数是5，同样将序列中5的倍数划掉，序列成了： 2 3 5 7 11 13 17 19 23 因为23小于5的平方，跳出循环. 结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。
实现代码
#include<iostream> #include<cstring> #include<cmath> using namespace std; const int N=10000000; bool prime[N]; int main() { memset(prime,true,sizeof(prime)); prime[0]=prime[1]=false; for(int i=2;i<=sqrt(N);i++) if(prime[i]) for(int j=i*i;j<N;j+=i) prime[j]=false; return 0; }线性筛 效率 O(N) 可以先估算下N之内素数个数，num≈ NlnN ，N越大越接近。
N素数个数N/lnN10025221,00016814510,0001,2291086100,0009,59286861,000,00078,4987238210,000,000664,579620421如果N＞ 107 ,就不适合打全部素数表。
实现代码
#include<iostream> #include<cstring> using namespace std; const int N=10000000; bool visit[N]; int prime[N/15];//保存素数，可以先估算个数减少空间开销 int main() { memset(visit,true,sizeof(visit)); visit[0]=visit[1]=false; int num=0; for(int i=2;i<=N;++i) { if(visit[i]) prime[++num]=i; for(int j=1;j<=num && i*prime[j]<=N;++j) { visit[i*prime[j]]=false; if(i%prime[j]==0)//!!!! break; } } cout<<"素数个数为："<<num<<endl; return 0; }因为 每一个合数都可以表示为若干个质数之积 if(i%prime[j]==0) break;保证了每个合数都能被它最小的一个质因子筛掉，所以大大提高了效率。 例如x为偶数，只需要被x/2筛就好。 对于奇数，假设i为9时，prime素数表里有2、3、5、7，先筛掉2*9=18，然后筛掉3*9=27，判断9%3==0，跳出。这是因为9可以分成3*3，如果继续晒5*9，相当于筛3*3*5=3*15，所以在i=15的时候筛就好，而埃氏筛法就没有这个优化。
互质数:公因数只有1的两个非零自然数。 费马小定理 对于任意正整数a，假如p是质数，且gcd(a,p)=1，那么 ap−1 %p≡1。
即：假如a是正整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。 ap−1 %p=1是p为质数的必要条件而非充分条件！！ 卡迈克尔数 对于任意正整数a，假如p是合数，且gcd(a,p)=1，那么 ap−1 %p≡1。
根据费马小定理和卡迈克尔数可以知道有些能满足费马小定理的数（p），不一定是质数,也就是说根据费马小定理判断素数并不一定可靠，但我们可以多测几个a的值增大正确率。
利用上述结论，对于给定的整数p，可以设计一个素数判定算法。 1. 随机选取整数a，2 ≤ a ≤ n-1，计算d= ap−1 %p。 当d不等于1时，n是合数； 当d等于1时，n则很可能是素数，对于本次判断来说，判断错误的概率为1/2。 2. 如此重复多次，可以将判断错误的概率降低至期望值以下。
那么现在又有了一个新问题，当p很大时，如何计算 ap−1
幂运算 如计算 213 ,则传统做法需要进行12次乘法。
long long power(long long a,long long p) { for(int i=1;i<p;i++) a*=a; return a; }这样的算法未免太慢，我们可以优化一下。 当我们计算出2*2时,我们可以把结果保存下来,这样就变成了 4*4*4*4*4*4*2 再把4*4的结果保存下来 16*16*16*2 再把16*16的结果保存下来 256*16*2
整理下这种优化思路，可以这样表示 当指数为奇数时，如 213 ，我们把算式优化为 2* (2∗2)12/2 ，也就是2* 46 当指数为偶数时，如 46 ，我们把算式优化为 (4∗4)6/2 ，也就是 163 继续这么做，算式变成了 16* (16∗16)2/2 ，也就是16*256 因此我们把过程中指数为奇数的积保存下来（2*16）乘以最后的值（256）就是所要的答案。
快速幂
long long qpow(long long a,long long p) {//计算a^p long long tmp=1;//保存过程中指数为奇数的乘积 while(p) { if(p&1)// 判断p是否奇数，偶数的最低位必为0 tmp*=a; a*=a; p>>=1; } return tmp; }有了快速幂的算法，我们是否可以用来计算 ap−1 ？当然还是不够的！当p很大时， ap−1 会超过数据的表示范围，但我们要的只是 ap−1 %p的结果，因此对快速幂的算法改进一下，用”蒙格马利”快速幂取模算法。
需要的模运算知识 (a*b)%m = [(a%m)*(b%m)]%m (a+b)%m = (a%m+b%m)%m
Montgomery快速幂模
long long Montgomery(long long a,long long p,long long m) {//计算a^p%m long long tmp=1; a%=m; while(p) { if(p&1) tmp=(tmp*a)%m; a=(a*a)%m; p>>=1; } return tmp; }根据费马小定理判断大素数 因为有gcd(a,p)=1的要求，a可以不是素数，可以增大素数表来提高准确率。
bool isprime(int n) { if(n<2) return false; int prime[]={2,3,5,7,11,17,19,23,29,31},len=10; for(int i=0;i<len&&prime[i]<n;++i) if(Montgomery(prime[i],n-1,n)!=1)//Montgomery快速幂模 return false; return true; }由于有卡迈克尔数，根据费马小定理来判断素数是不准确的。 例如252601这个数，它还有因子41，明显不是个素数，但通过了费马小定理的测试，我们可以在素数表中加入41，这样就不能通过了。但是这样我们就不能确定合理的素数表范围，而且需要测试很多组数据。 我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究，并加以扩展，总结出了多种快速有效的素数测试方法，目前最快的算法是拉宾米勒测试算法，下面介绍拉宾米勒测试。
拉宾米勒算法
1.如果判断n是否为素数，先判断n是否为1、2、3以及2、3的倍数，能删去很多数 2.令n-1= 2r *d，取不同的a(2 ≤ a ≤ n-1)，对r从0到最大，满足 ad %n≡1，此处要分情况
d为奇数，若同余1，可能为质数d为偶数，若同余-1，可能为质数循环后不符合上述情况，必为合数对于取a的值 通常2，7，61就可计算至2^32数量级 若还需更大，则计算2，3，5，7，11.
反正我也不会证，看模版吧
long long Montgomery(long long a,long long p,long long m) {//计算a^p%m long long tmp=1; a%=m; while(p) { if(p&1) tmp=(tmp*a)%m; a=(a*a)%m; p>>=1; } return tmp; } bool Miller_Rabbin(long long a,long long n) { long long r=0,d=n-1; while(!(d&1))//找到奇数 { d>>=1; r++; } long long k=Montgomery(a,d,n);//Montgomery快速幂模 if(k==1) return true;//同余1 for(int i=0;i<r;i++,k=k*k%n) if(k==n-1) return true;//同余-1 return false; } bool isprime(long long n) { if(n==2||n==3||n==7||n==61) return true; if(!(n&1)||n%3==0||n==1) return false; int prime[3]={2,7,61}; for(int i=0;i<3;i++) if(!Miller_Rabbin(prime[i],n)) return false; return true; }这个方法只能测 263−−−√ 类型的数，因为在快速幂模运算时（a*a）或者（tmp*a）相乘可能会超过long long类型的数据范围。 能测 263 /2类型的改进版 把a*a这样的数据改成a个a相加，每次相加（仿照快速幂写个快速乘法）都取模，就不会超过long long类型的范围。
long long mul(long long a,long long b,long long m) {//计算(a*b)%m long long tmp=0; while(b) { if(b&1) tmp=(tmp+a)%m; a=(a+a)%m; b>>=1; } return tmp; } long long Montgomery(long long a,long long p,long long m) {//计算a^p%m long long tmp=1; a%=m; while(p) { if(p&1) tmp=mul(tmp,a,m); a=mul(a,a,m); p>>=1; } return tmp; } bool Miller_Rabbin(long long a,long long n) { long long r=0,d=n-1; while(!(d&1))//找到奇数 { d>>=1; r++; } long long k=Montgomery(a,d,n);//Montgomery快速幂模 if(k==1) return true;//同余1 for(int i=0;i<r;i++,k=k*k%n) if(k==n-1) return true;//同余-1 return false; } bool isprime(long long n) { if(n==2||n==3||n==5||n==7||n==11) return true; if(!(n&1)||n%3==0||n==1) return false; int prime[5]={2,3,5,7,11}; for(int i=0;i<5;i++) if(!Miller_Rabbin(prime[i],n)) return false; return true; }原文地址：高效判断素数方法 所谓孪生素数指的是间隔为2的相邻素数，它们之间的距离已经近得不能再近了。 若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数 证明： ∵ n-1和n+1是素数 ┈┈┈┈┈ ① ∴ n-1和n+1是奇数 ∴ n是偶数，即n是2的倍数 ┈┈┈┈┈ ②
假设n不是3的倍数，得： n=3x+1 或 n=3x+2 如果n=3x+1，则n-1=3x，与①违背，故n≠3x+1； 如果n=3x+2，则n+1=3(x+1)，与①违背，故n≠3x+2； ∴假设不成立，即n是3的倍数，又有②得结论： n是6的倍数。
由上面的规律可以推出下面结论： 若x≧1且n=6x-1或n=6x+1不是素数，那么n一定不是2和3的倍数。 证明： ∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。 ∴n一定不是2和3的倍数。 素数出现规律： 当n≧5时，如果n为素数，那么n mod 6 = 1 或 n mod 6 = 5，即n一定出现在6x（x≥1）两侧。 证明： 当x≥1时，有如下表示方法： ┈┈ 6x，6x+1，6x+2，6x+3，6x+4 ,6x+5，6(x+1），6(x+1)+1┈┈ 不在6x两侧的数为6x+2，6x+3，6x+4，即2(3x+1)，3(2x+1)，2(3x+2)，它们一定不是素数，所以素数一定出现在6x的两侧。
