[编程笔记]-Prime_Basis质数基础

前言

进入数学部分了

概念

质数，指的是大于1的只有1和本身两个因数的数，又叫素数。

判定

试除法

基础版

就是把所有二以上的数一个一个试，时间复杂度O(n)。

bool prime(int num){
    if(num<2)return false;
    for(int i=2;i<num;i++){
        if(num%i==0)return false;
    }
    return true;
}

很明显，太慢了。

优化版

优化：

若d为n约数，那么n/d也为n约数。所以d和n/d成对出现。因此我们只需要枚举每一对中较小的元素，整理得：
d*d<=n

时间复杂度

O(sqrt(n))

写法推荐

1. i<=sqrt(n)，不推荐，每次都要执行一次sqrt，很慢。
2. i*i<=n，不推荐，如果n足够大，很容易溢出。
3. i<=n/i，推荐，不会溢出，也足够快。

代码

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

其他判定方法

一般优化的就是各种质数筛，什么线性筛、埃氏筛之类的，详见下方质数筛部分。

更高阶的算法，肯定不在这里讲。

分解因数

试除法

没错还是它，质数运算的简单暴力算法——试除法。

基础版

从2开始一直试到n，每次都去让n除以这个数，除到没法除为止，每次的除数就是一个因数。然后接着下一个数。

时间复杂度O(n)。

vector<int> dpf(int num){
    vector<int> vec;
    for(int i=2;i<=num;i++){
        while(num%i==0){
            vec.push_back(i);
            num/=i;
        }
    }
    return vec;
}

优化版

原理

n中最多只包含一个大于sqrt(n)的质因子。

证明

反证法，要是有两个，乘起来就大于n了不是吗hh

优化

那么因数就枚举到sqrt(n)即可。若最后n>1，那么n自己就是那个大于sqrt(n)的质因子。

时间复杂度

最好O(logn)，最坏O(sqrt(n))

代码

vector<int> dpf(int num){
    vector<int> vec;
    for(int i=2;i<=num/i;i++){
        while(num%i==0){
            vec.push_back(i);
            num/=i;
        }
    }
    if(num>1)vec.push_back(num);
    return vec;
}

质数筛

朴素做法

先创建一个质数序列，从2开始，一开始所有数都在里面。

然后从2一个一个往后走，每一次都把它所有倍数从序列里筛掉。

O(nlogn)

int get_prime_num(int num){
    int cnt=0;
    int prime[N];
    bool st[N]={false};
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[++cnt]=i;
        }
        for(int j=1;i*j<=n;j++){
            st[i*j]=true;
        }
    }
    return cnt;
}

埃氏筛(Eratosthenes)

只有质数需要把所有倍数筛掉。

O(nloglogn)

int get_prime_num(int num){
    int cnt=0;
    int prime[N];
    bool st[N]={false};
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[++cnt]=i;
            for(int j=1;i*j<=n;j++){
                st[i*j]=true;
            }
        }
    }
    return cnt;
}

线性筛(Euler)

筛法

也是从2枚举到n（令当前为i），如果i没有被筛掉，就添加为质数。

但不管是不是质数，都进行一次循环，遍历当前所有不大于n/i的质数，把他们的i倍筛掉。若当前质数是i的因数，退出循环。

原理

线性筛中，n只会被最小质因子筛掉

证明

情况1：i%pj==0

因为是从小到大枚举的所有质数，所以pj一定是i的最小质因子，pj也就一定是pj*i的最小质因子。

情况2：i%pj!=0

同理，pj一定小于i的最小质因子，pj也就一定是pj*i的最小质因子。

---

对于一个合数x，假设pj是x的最小质因子，那么当i枚举到x/pj，就会把x筛掉。

之所以遍历所有不大于n/i的质数，是为了pj*i不超过最大数n…

当i%pj==0时，那么之后的比pj大的质数就大于i的最小质因数了，因为n只会被最小质因子筛掉，而n=pj*i，因此i的最小质因数才是n的最小质因数，所以直接退出循环即可。

之所以不用添加j<=cnt：当i为质数，当pj==i时自己会停下。当i为合数，当pj是i的最小质因数时会停下，而i之前所有质数都是已经确定了的，i之后的也不会遇到。

时间复杂度

O(n)

代码

int get_prime_num(int num){
    int cnt=0;
    int prime[N];
    bool st[N]={false};
    for(int i=2;i<=num;i++){
        if(!st[i])prime[++cnt]=i;
        for(int j=1;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
    return cnt;
}

完结撒花o(￣︶￣)o