算法提高篇--数学基础（二）：质数（素数）

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]时中断循环，确保每个数只被最小质因数筛除。    }  } }