当前位置: 首页 > 工具软件 > Sieve > 使用案例 >

SIEVE 线性筛

周锐
2023-12-01

今天来玩玩筛

英文:Sieve

有什么筛?

这里介绍:素数筛,欧拉筛,约数个数筛,约数和筛

为什么要用筛?

顾名思义,筛就是要漏掉没用的,留下有用的。最终筛出来1~n的数的一些信息。

为什么要用线性筛?

考虑最基础的线性筛素数,是O(n)的。

而一般的做法是:

1.对于每个m暴力枚举1~sqrt(m)看能否被整除。O(nsqrt(n))

2.对于每个找到的素数,用它去将所有它的倍数的数都干掉。O(nlogn)

但是,即使是第二种,也有一个log

这是因为一个合数会被它的所有质因子筛一次。要重复质因子个数次,除第一次之外都没用。

所以用线性筛

 

线性筛原理:

一个算法,使得每个合数只被它的最小质因子筛一次。

怎么保证呢?

 

素数线性筛:

先看代码:

#include<bits/stdc++.h>
using namespace std;
const int N=10000000+10;
int ps[N],cnt;
bool v[N];
int n,m;
void sieve(){
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            ps[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*ps[j]>n) break;
            v[i*ps[j]]=1;
            if(i%ps[j]==0) break;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    sieve();
    v[1]=1;
    int t;
    for(int i=1;i<=m;i++){
        scanf("%d",&t);
        if(v[t]) printf("No\n");
        else puts("Yes");
    }
    return 0;
}

看不懂...................

解释:
对于一个质数,之前没有被标记。肯定只会有一次查到。把它记录到素数集合里去。

然后,不论这个数是否为质数,都将已有的质数从1~cnt循环一遍,把所有的i*ps[j]标记。

当i*ps>n break,可以理解。

当i%ps==0 break.???

这个时候,ps和i不互质了,而ps第一次整除i,所以ps就是i的最小质因数。叫他ps0

而之后,ps更大,ps*i的最小质因数就不是ps了。因为i里有ps0,这个合数就等着以后i更大了,通过ps0筛掉。

ps再大,后面的ps*i的最小质因数都不是ps,所以之前直接break掉就好。

由于每个合数只会被i*ps的形式找到一次(那一次的ps就是这个合数的最小质因子)。而内层循环每一次都对应一个将v[ps*i]=1的操作。

所以内层循环均摊O(1),总共O(n)

完毕。

 

欧拉线性筛:

代码:fai(i) 1~i中和i互质的数的个数。

可以容斥推出公式:假设:i=p1^q1*p2^q2*....pn^qn

那么,fai(i)=p1^(q1-1)*(p1-1) * p2^(q2-1)*(p2-1) * ......pn^(qn-1) * (pn-1)

证明不是本篇想讲的。

void sieve(){
   fai[1]=1; for(int i=2;i<=n;i++){ if(v[i]==0){ fai[i]=i-1; pri[++cnt]=i; } for(int j=1;j<=cnt;j++){ if(i*pri[j]>n) break; v[i*pri[j]]=1; if(i%pri[j]==0) { fai[i*pri[j]]=fai[i]*pri[j];break; } else{ fai[i*pri[j]]=fai[i]*(pri[j]-1); } } } }

并不想从积性函数性质入手解释。

显然的,当处理到fai[i]的时候,i的值应该就知道了。i是质数就现成赋值。

考虑公式。

当i%ps==0 时,i的质因子中有ps,那么i*ps的质因子ps的次数就大于一,那么,就是fai[i]*ps了

否则,i*ps 的 ps的次数就是1,那么,ps^(1-1)*(ps-1)=(ps-1) 所以是fai[i]*(ps-1)

之后的各种操作基于线性筛的要求和特质。(即每个数只被它的最小质因子筛一次)

例题:SDOI2008 仪仗队

 

约数个数线性筛:

推荐:线性筛约数个数和、约数和

设x=p1^q1*p2^q2*....pn^qn

要知道公式:个数=(q1+1)*(q2+1)*...*(qn+1) 乘法原理就可以知道。

设t[i]表示i的约数个数

设e[i]表示i的最小素因子个数

①i是质数:t[i]=2,e[i]=1;

②i%pj!=0 这个时候,pj里面没有i,根据积性函数,或者乘法原理,t[i*pj]=t[i]*t[pj]=2t[i];

而 e[i*pj]=1

③i%pj==0 这个时候,pj里面至少有一个i,i也是pj的最小质因子。

t[i*pj]=t[i]/(e[i]+1)*(e[i]+2) 考虑公式,i*pj只在pj的位置上加了1,所以先除掉,再乘上去。

e[i*pj]=e[i]+1 最小素因子个数多了一个。

 

约数和的线性筛:

推荐:线性筛 [约数个数/约数和]

(很详细的解释)

设x=p1^q1*p2^q2*....pn^qn

首先还是要知道公式:和=(1+p1^1+...+p1^q1)*(1+p2^1+...+p2^q2)*...*(1+pn^1+...+pn^qn)

证明很简单,加数的个数显然就是约数个数,每次选择就是这个约数个数的质因数分解形式,数值就是这个约数的数值。

设t[i]表示i的约数和

设e[i]表示i的最小素因子对约数和的答案的贡献,即:(1+p1^1+...+p1^q1)(假设p1是最小质因子)

①当i是质数的时候,t[i]=i+1;e[i]=i+1;

②i%pj!=0 根据公式、积性函数性质 : t[i*pj]=t[i]*t[pj]

e[i*pj]=1+pj;

③i%pj==0

t[i*pj]=t[i]/e[i]*(pj*e[i]+1)

证明:考虑公式,i里面有pj的贡献,乘了一个pj,相当于多了一个pj^(qj+1)所以除掉后,乘上错位,再加一

而 e[i*pj]=e[i]*pj+1

就这样。代码参考上面的写就是了,没什么难度。

 

莫比乌斯函数筛:

知道定义就好说:

μ(i)={

0 i有平方因子

1 i的质因子个数为偶数

-1 i的质因子个数为奇数

}

根据定义直接筛就好了。

void sieve(){
    u[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            u[i]=-1;
            pr[++cnt]=i;            
        }
        for(int j=1;j<=cnt;j++){
            if(pr[j]*i>N) break;
            vis[pr[j]*i]=1;
            if(i%pr[j]==0) {
            u[pr[j]*i]=0;break;
            }
            else u[pr[j]*i]=-u[i];
        }
    }
}

例题:bzoj2440 完全平方数

转载于:https://www.cnblogs.com/Miracevin/p/9251873.html

 类似资料: