质数
参考文献：《信息奥赛一本通》，《算法竞赛指南》
简单概述？
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。首先我们都知道，质数是一个正整数，无法被除了1和它自身之外的任何自然数整除，若不满足，则这个正整数为合数。
算术基本定理：
每一个大于1的正整数都可以唯一分解成有限个质数的乘积，如：
5=1*5 6=2*3 18=2*2*3 .......
质数分布定理：
（说实话这个我还没搞懂，等我搞懂再来补充）
质数判定：
试除法
若一个正整数A为合数，则必定存在一个能整除A的数T，其中2 <= T <= sqrt(A);
证明：我们可以用·反证法· ，即假设以上的结论不成立，则必定存在T满足sqrt(A)+1 <= T <= A-1；
因为 A / T == K，且T整除A，则K也一定整除A，但是K一定在2 <= K <=sqrt(A)中，所以假设不成立，原命题成立。(sqrt 为开根号）
根据这个定理我们可以发现，只要扫描从2到sqrt(A)间所有整数是否整除A，可以就为合数，否则为质数。
代码如下(时间复杂度为 O(sqrt(N)) )
bool is_prime(long n){ for(long i=2;i<=sqrt(n);i++) if (n%i==0) return 0; return 1; }
当然我们可以用“Miller-Robbin”，多次判定出错率接近0，在这里就不介绍了。
质数的筛选
No.1 Eratosthenes 筛法 （简称埃氏筛）
它的思想是，只要是质数的倍数就一定不是质数， 因为质数的倍数它一定可以表示成某个质数*倍数形式，不满足质数的定义。
操作：从小到大枚举每一个质数，但只要是质数的倍数就全部标记成非质数,整数1特殊处理。
例如过程如下：
2 3 4 5 6 7 8 9 10 11 12 ...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
2 3 4 5 6 7 8 9 10 11 12...
但是事实上6 会被2 和 3同时标记为合数，则说明小于x2（x的平方）的x的倍数在之前扫描更小的数时就已经标记过了，所以我们可以优化这个筛法，
对于每一个x，把 >= x2的x的倍数标记为合数就可以了，即扫描x时从x2开始标记就行。
算法复杂度为O(n logn logn)，接近线性
bool v[MAXN]; //合数标记 void primes(long n){ memset(v,0,sizeof v); for(long i=2;i<=n;i++){ if(v[i]) continue; cout<<i<<endl; //i是质数 for(long j=i;j<=n/i;j++) v[i*j]=1; //累计倍数 }
}
No.2 线性筛法
即使是优化后的Eratosthenes算法，它还是会有重复标记发生，例如12 还是会被2，3重复标记，它时间复杂度较高的根源是它无法唯一确定某个合数的产生方式。
而线性筛法是通过“从大到小累积质因子”的方法去标记每个合数，因为每个合数只会被它的最小质因子筛一次，时间复杂度为O(N)。原理是算术基本定理
代码如下
long v[MAXN],prime[MAXN]; void primes(long n){ memset(v,0,sizeof v); //v表示最小质因子 long m=0;//质数数量 for(long i=2;i<=n;i++){ if(v[i]==0){//i为质数 v[i]=i; prime[++m]=i; }
//给i乘上一个质因子 for(long j=1;j<=m;j++){ if(prime[j]>v[i] || i*prime[j]>n) break;//若这个质数大于i的最小质因子，或者超出n的范围，就终止循环 v[prime[j]*i]=prime[j]; //这样就可以得到prime[j]必定为prime[j]*i的最小质因子 （prime[j]<=v[i]) } } for(long i=1;i<=m;i++) printf("%ld\n",prime[i]); }
质因数分解
它要根据算数基本定理来分解
即
任何一个大于1的正整数都能唯一分解为有限个质数的乘积（ai为正整数，pi为质数，p1<p2<......<pn）
方法：试除法
我们可以扫描从2~sqrt(N)的每个数k，并判断k是否整除N，若成立，则继续除下去直到N无法被k整除 ，即除去N中所有的因子并记录除去的k值个数
这样的话，N的合数因子一定在扫描到它之前就被除去了，因为根据算数基本定理，这个合数因子也可以被分解质因数，而它的质因数也是原合数的质因数，
所以在之前就必定被抹杀了......
当然如果N无法被2~sqrt(N)整除，则说明N是质数，应注意不要漏了。
时间复杂度为O( sqrt(N) )。
void divide(long n){ long m=0; //质数数量 for(long i=2;i<=sqrt(n);i++){ if(n%i==0){ //若成立，则i必定为质数 prime[++m]=i; a[m]=0; while(n%i==0) n/=i,a[m]++; } if(n>1) //说明n本身为质数，无需分解 p[++m]=n;a[m]=1; } for(long i=1;i<=m;i++) printf("%ld^%ld\n",p[i],a[i]); }
就这样吧......
比较菜，若有问题望及时提出谢谢。
