【学习笔记】线性筛的五种基本用法

SM_929hz · 2025-12-10 16:25:39 · 算法·理论

线性筛定义

线性筛（欧拉筛）是一种高效筛选质数的算法，能在 \operatorname{O}(n) 的时间复杂度内找出 1 到 n 之间的所有素数。

具体操作

从小到大枚举每个数：

1. 如果当前的数没有被划掉，那么这个数一定是质数，就记录下来。
2. 枚举已经记录的质数：\ 合数没有越界，则划掉该合数。\ 如果 p_j \mid i，保证合数只被最小质因子划掉。\ 若 i 为质数，最多枚举到自身就中断；\ 否则最多枚举到自身的最小质因子就中断。

:::info[时间复杂度：\operatorname{O}(n)]{open} 每个合数只被标记一次。\ 线性筛的核心思想是： 每个合数仅被其最小质因子标记一次，这种机制避免了埃氏筛中重复标记合数的问题。 所以时间复杂度为 \operatorname{O}(n)。 :::

四种基本用法

1. 质数筛

这是最基本也是最经典的用法了，具体操作同上。\ 例题。

Code

#include<bits/stdc++.h>
using namespace std;
bool pd[100000005];
int p[6000010],cnt,n,q;//p为存储质数的数组 
void get(int n){//线性筛 
    memset(pd,1,sizeof(pd));//初始化默认全是质数 
    pd[1]=0;//1不是质数 
    for(int i=2;i<=n;i++){
        if(pd[i])//如果i是质数(前面的都没筛掉) 
            p[++cnt]=i;//存储质数 
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            pd[i*p[j]]=0;//标记合数 
            if(i%p[j]==0)//避免重复的标记 
                break;
        }
    }
}
int main(){
    scanf("%d%d",&n,&q);//根据题意 
    get(n);
    while(q--){
        int k;
        scanf("%d",&k);
        printf("%d\n",p[k]);
    }
    return 0;
}

2. 欧拉函数

欧拉函数。\ 我们知道欧拉函数的公式为：

\varphi(n)=n \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \cdots \times \frac{p_{s}-1}{p_{s}}

因为欧拉函数的公式具体为：n 乘上每个质因子 p 的 \frac{p-1}{p}。\ 那么我们就可以通过线性筛的性质：每次只筛到最小的质因子就跳过，来优化欧拉函数。

具体的：

若 i 为质数，那么 \phi_i=i-1，并记录质数。\ 在线性筛中，每个和数 m 都是被最小的质因子筛掉的。\ 设 p_{j} 是 m 的最小质因子，则 m 是通过 m=p_{j}\times i 筛掉的。

1. 若 p_j \mid i，则 i 包含了 m 的所有质因子。\
2. 若 i 不能被 p_{j} 整除，则 i 和 p_{j} 是互质的。\

Code

const int N=1000005;
int p[N],vis[N],cnt,phi[N];
void g_phi(int n){//欧拉筛法求1到n的phi值 
    phi[1]=1;//1的欧拉函数值为1 
    for(int i=2;i<=n;i++){
        if(!vis[i]){//i为质数 
            p[++cnt]=i;//记录质数 
            phi[i]=i-1;//指数的phi值为i-1 
        }
        for(int j=0;i*p[i]<=n;j++){//用i和所有质数p[j]的乘积筛 
            int m=i*p[j];
            vis[m]=1;//m为非质数 
            if(i%p[j]==0){//如果i为p[j]的倍数 
                phi[m]=p[j]*phi[i];//根据欧拉函数的积性性质计算 
                break;//跳出内层循环 
            }
            else
                phi[m]=(p[j]-1)*phi[i];
        }
    }
}

3. 筛法求约数个数

约数个数的公式

设 d(n) 为 n 的约数个数。

Code

const int N=1000005;
int p[N],vis[N],cnt,a[N],d[N];
void g_ys(int n){
    a[1]=1,d[1]=1;//1初始化 
    for(int i=2;i<=n;i++){
        if(!vis[i]){//i为质数
            a[i]=1,d[i]=2,p[++cnt]=i;
        }
        for(int j=0;i*p[j]<=n;j++){
            int m=i*p[j];
            vis[m]=1;//标记合数
            if(i%p[j]==0){//i能被p[j]整除
                d[m]=d[i]/a[m]*(a[m]+1);//更新约数公式
                a[m]=a[i]+1;
                break;
            }
            else//i不能被p[j]整除
                d[m]=d[i]*2,a[m]=1;//新质因子
        }
    }
}

4. 筛法求约数之和

约数和定理

若 n=\prod_{i=1}^{s}p_i^{a_i}，则 f(n)=\prod_{i=1}^{s}\sum_{j=0}^{a_i}p_i^j。

:::info[人话]{open} 一个数 n 可以分解为质因数的乘积形式，p 是 n 的不同质因数，a 是对应质因数的指数。\ 要计算 n 的所有约数之和，就需要对每个质因数 p_i，计算从 p_i^0 次方到 a_i 次方的和 \sum_{j=0}^{a_i}p_i^j，然后将这些和相乘，得到的结果就是 n 的约数和。 :::

:::info[例子] 假设 n 为 24。\

2. 若 i 不能被 p_j 整除，则 m 比 i 多一个不同的质因子 p_j：\ \mu_m=-\mu_m。

Code

const int N=1000005;
int p[N],vis[N],cnt,mu[N];
void g_f(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){// i为质数 
            p[++cnt]=i,mu[i]=-1;
            // 统计质数；它只有一个质因子，所以为-1。
        }
        for(int j=0;i*p[j]<=n;j++){
            int m=i*p[j];
            vis[m]=1;// 标记合数
            if(i%p[j]==0){// i能被p[j]整除
                mu[m]=0;
                break;// 上文描述 
            }
            else
                mu[m]=-mu[i];// 上文描述 
        }
    }
}