算法提高篇--数学基础（二）：质数（素数）
1、概述
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。其余的大于1的自然数叫做合数。
质数有无穷多个，但分布比较稀疏，不大于n的素数约有(n/In(n))个。
2、质数判定
判断一个数是否是质数的方法可按照如下代码方式实现：
bool isPrime(int n){ if(n==1) return false; for(int i=2;i<n;++i) if(n%i==0) return false; return true;}以上算法的时间复杂度为O(n)，如果n>10^7，那么很容易就TLE了。可以进一步优化为O(sqrt(n))的复杂度。代码如下：
bool isPrime(int n){ if(n==1) return false; for(int i=2;i*i<=n;++i) if(n%i==0) return false; return true;}我们稍微证明以上算法的合理性，即对一个数n，如果能分解为a*b的形式，且a<b。则a*a<a*b =n。若存在一个大于sqrt(n)的数b，可以作为整除n，那必然整除的结果是小于sqrt(n)的，即它们是以sqrt(n)为中心成对出现的。所以，我们只需要判断到sqrt(n)即可，也就是代码中(i*i<=n)。
3、牛刀小试
我们尝试用上述方法来解决下面一道质因数分解的题目：
这是一道送分题，考察的就是在O(sqrt(n))内得到质因数。题目已经说明了n可以分解为两个质因数，因此我们可以直接运用判断质数的方法求得。参考代码如下：
#include<cstdio>#include<iostream>using namespace std;int main(){long long n;scanf("%lld",&n);for(int i=2;i*i<=n;++i){if(n%i==0){cout<<n/i<<endl;return 0;}}return 0;}
稍微做个小扩展：整数唯一分解定理：若整数n≥2，那么n一定可以唯一地表示为若干质数的乘积。
4、埃氏筛法
如果能够事先准备好质数表，就可以帮助我们更有效地求解质数的相关问题。下面我们来看看埃拉托色尼筛法（Sieve of Eratosthenes）。
埃拉托色尼筛法又称为埃氏筛法：每个合数a一定可以写成p*x的形式，其中p为质数，x是倍数（x≠1），对于每一个1~n的素数p，枚举倍数x，把p*x标记为合数，这就是埃氏筛法。
在进行筛选时，可以做一个小小的改进，对于质数p，只筛倍数x≥p的数。因为如果x<p，则x中一定有比p小的质因子，p*x会在前面筛选过程中被筛选出来。时间复杂度为O(nloglogn)。实现方式如下：
void eratos(int n){ int i,j; memset(isPrime,true,sizeof(isPrime)); isPrime[0] = isPrime[1] = false; for(int i=2;i*i<=n;++i){ if(isPrime[i]){ for(int j=i*i;j<=n;j+=i){ isPrime[i] = false; } } }}5、学以致用
我们以一本通1619题为例来实践埃氏筛法。
如题，R最大差不多去到了2^31，每一个数都要去判断是否数质数的话，那在规定时间内是无法得出[1,R]的所有素数的。我们使用筛法求出[2,sqrt(R)]，大概是[2,50000]，因为50000^2>2^31的所有素数，然后对每个素数p，把[L,R]中能被p整除的数标注筛掉，即isPrime(i*p)=false，其中(L/p≤i≤R/p)。剩下为true的素数之间进行相邻两者间比较，找出差最小和最大的一组即可。此外，这题还用了j-L来使得数组下降，以免数组太大而爆掉。这里利用了R-L<=10^6这个限制，将isPrime数组设置大小为2*10^6左右就绰绰有余了。代码如下：
#include<bits/stdc++.h>using namespace std;const int N = 2e6+5;const int M = 50001;//50000^2>2^31typedef long long ll;bool isNoPrime[M];//筛选非质数为truebool isPrime[N];//确定区间内找质数ll prime[M];//质数存进来在区间筛合数void init(){memset(isNoPrime,0,sizeof(isNoPrime));isNoPrime[0]=isNoPrime[1]=true;//非质数for(ll i=2;i*i<M;++i){if(!isNoPrime[i]){//如果i是质数，把其倍数筛去//这里只筛大于等于i的平方的数。//设j = x*i;(x为倍数)。//如果x<i。则作为x肯定有比i小的质因数p//即x = yp。在用p筛质数的时候，j = (y*i)*p，已经被筛了一遍//因此我们从x>=i开始找未被筛出的合数。for(ll j=i*i;j<M;j+=i){isNoPrime[j] = true;//将i的倍数筛出。}}}for(ll i=0,j=0;i<M;++i){if(!isNoPrime[i]){prime[j++] = i;//将质数入数组}}}void solve(ll L,ll R){memset(isPrime,false,sizeof(isPrime));if(L==1){isPrime[0] = true;//true代表合数，筛出}for(ll i=0;prime[i]*prime[i]<=R;++i){ll t = L/prime[i];//继续筛选ll j = t*prime[i];if(t<=1){//目的是找最接近L的数开始筛出j = prime[i]*2;}for(;j<=R;j+=prime[i]){if(j-L>=0){//j肯定要满足比L大isPrime[j-L] = true;//true代表合数，筛出，区间下降，否则数组不够大}}}ll mll = 0x7fffffff,maxt = 0;ll first = -1;ll ca=-1,cb=-1,ma=-1,mb=-1;for(ll i=L;i<=R;++i){if(!isPrime[i-L]){//注意区间已下降if(first!=-1){if(i-first<mll){mll = i-first;ca = first;cb = i;}if(i-first>maxt){maxt = i-first;ma = first;mb = i;}}first = i;}}if(ca!=-1){printf("%lld,%lld are closest, %lld,%lld are most distant.\n",ca,cb,ma,mb);}else{printf("There are no adjacent primes.\n");}}int main(){ll L,R;init();while(~scanf("%lld %lld",&L,&R)){solve(L,R);}return 0;}
6、欧拉筛法（线性筛）
在埃氏筛法中，当p等于2、3、5的时候，分别将30这个数筛了三次，即2*15,3*10,5*6。能否有方法对每个数最多只筛一次呢？如果每个合数只被它的最小质因数筛除，如30只被2筛除，则可以实现效率的大幅度提高。这种方法，叫做欧拉筛法，也叫做线性筛。方法如下：
我们枚举2~n的中的每一个数i：
1）、如果i是质数，则将i保存到质数表prime[j]中。
2）、利用i和质数表中的质数prime[j]筛除i*prime[j]，为了确保i*prime[j]只被prime[j]筛除一次，要确保i中不能有比prime[j]还小的质数。
其模板如下：
void eulerSieve(int n){ memset(isPrime,true,sizeof(isPrime)); prime[0] = 0;//记录当前质数个数 for(int i=2;i<=n;++i){ if(isPrime[i]){ //1、把质数保存在质数表prime中 //2、更新prime[0]中保存的质数个数信息 prime[++prime[0]] = i; } for(int j=1;j<=prime[0]&&i*prime[j]<=n;++j){ isPrime[i*prime[j]] = false;//筛除i*prime[j]，注意i此时会大于或等于质数表中的质数 if(i%prime[j] == 0)break;//当i中含有质因数prime[j]时中断循环，确保每个数只被最小质因数筛除。 } } }