数学知识—— 一.质数

1.定义

若一个正整数无法被除1和它自身以外的自然数整除，则该数为质数（或素数），否则该数为合数。
1既不是质数也不是合数。
由定义可得质数的一个性质：只有1和它本身两个因数。
补充：对于一个足够大的整数N，不超过N的质数大约有N/㏑N个。即每㏑N个数中有1个质数。

2.判定质数

根据定义：素数就是一个数除了1 和他本身没有其他因数的数叫做质数。
于是我们对于一个N,可以可以从2枚举到N−1，从而判断这个数是不是质数。

bool Is_prime(int n);{
    if(n==1)return false;
    if(n==2)return true；
    for(int i=2;i<n;i++)
        if(n%i==0)return false;
        return true;
}

时间复杂度O(n);
对于上述程序显然不能满足我们的需求，如N较大时，这样的程序肯定容易超时，要想办法优化以上程序。

优化

我们不难发现N的因数是成对出现的，所以对于任何一个整数N，我们只需要从1枚举到sqrt(N)就可以了。
于是代码如下：

bool Is_prime(int n){
    if(n==1)return false;
    if(n==2)return true;
    for(int i=2;i<=n/i;i++)
    if(n%i==0)return false;
    return true;
}

时间复杂度o(sqrt(n))
ps.关于i<=n/i ： 如果当i很大，还直接计算i*i时，可能会爆int，而计算n/i就没有这个问题，而且代码简洁（个人喜好而已）。

还可以优化的地方（常数级，一般可忽略）：
（1）除2以外的偶数一定不是质数。
（2）大于3的质数除以6的余数一定是1或5，但反过来说的话，这句话是错的。（反证法：大于3的数除以6余2一定是偶数，余3一定是3的倍数，余4一定是偶数。）
即大于3的质数与除以6的余数一定是1或5之间是充分不必要条件关系。（充分不必要条件：不懂请百度）

小结：在对于素数的判断时，一般用第一种的优化方法就可以了。
但是如果遇到了出题人卡常数，最好是用上补充的第二种方法。

3.质数的筛选

一般筛法：判断每个数是不是质数。

代码如下：

bool Is_prime(int n){
    if(n==1)return false;
    if(n==2)return true;
    for(int i=2;i<=n/i;i++)
    if(n%i==0)return false;
        return true;
}
const int N=100010
bool prime[N];
void make_prime(){
    for(int i=1;i<=N;i++)
        prime[i]=Is_prime(i);
    return;
}

时间复杂度O(N*sqrt(N));

代码简单易懂，但时间复杂度略高。不推荐使用。

常用筛法：Eratosthenes筛法（埃氏筛法）

基本思想：素数的倍数一定不是素数（根据素数的定义可轻松证明）

实现方法：用一个长度为N+1的布尔数组保存信息（true表示素数，false表示非素数）。

先假设所有的数都是素数（初始化为true），从第一个素数2 开始，把2的倍数都标记为非素数（更新为false），一直到大于N；然后进行下一趟，找到2 后面的下一个素数3，进行同样的处理，直到最后，数组中依然为true的数即为素数。

注意：1既不是质数也不是合数，1在初始化后直接更新为false；

此处有动图模拟该筛法

这种方法的实现有很多，这里展示本人最顺手的一种：

（原题：统计1~N之间的素数个数）

#include<bits/stdc++.h>
using namespace std;
bool s[4000000];
long long n,k;
int x,cnt=0;
void find(){
    memset(s,true,sizeof(s));
    s[1]=false; //1既不是质数也不是合数，1在初始化后直接更新为false
    for(int i=2;i<=k;i++){
        if(s[i]){
            int j=i+i;//通过累加来得到质数的倍数
            while(j<=k){
                s[j]=false;
                j+=i;
            }
        }
    }
}
int main(){
    cin>>k;
    find();
    for(int i=1;i<=k;i++){
        if(s[i])cnt++;
    }
    cout<<cnt;
    return 0;
}

此方法的复杂度为O(nloglogn)

代码较简单，时间复杂度接近线性，是最常用的质数筛法。

然而，分析上述代码，我们发现此方法还可以继续优化，因为上述的方法中，每一个有多组因数可能会被筛多次，例如：30 会被2,3,5各筛一次导致重复计算。根据该缺点，我们可以对此方法进行改进，得到更加高效的筛法：线性筛法。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int primes[N], cnt;
bool st[N];
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;//给每一合数确定唯一产生方式
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    int n;
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}

时间复杂度O(n)

代码理解难度略大，时间复杂度为线性，空间复杂度相对较高（多了个常数而已），若非出题人在时间上卡常数，一般情况下不常使用。

小结：三种筛法各有优势，可作为各位不同情况下的不同选择。

4.质因数分解

算数基本定理

任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积，即：

这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。
这个定理十分重要，以后我们还会再用到这个定理。

试除法

结合质数判定的“试除法”和质数筛选的“埃氏筛法”，我们可以扫描2~sqrt(N)之间的每一个整数d，若d能整除N，则从N中除掉所有的因子d，同时累计除去的d的个数。

因为一个合数的因子一定在扫描到这个合数之前就从N中被除掉了，所以在上述过程中能整除N的一定是质数，最终就得到了质因数分解的结果，易知时间复杂度为O(sqrt(N))。

特别的，若N每有被任何2~sqrt(N)的数整除，则N是质数，无需分解。

代码如下：

void divide(){
    m=0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){//i是质数
            p[++m]=i,c[m]=0;
            while(n%i==0)n/=i,c[m]++;//除掉所有的i
        }
    }
    if(n>1)//n是质数
        p[++m]=n,c[m]=1;
    for(int i=1;i<=m;i++)cout<<p[i]<<" "<<c[i]<<endl;
}