素数筛法

埃氏筛法:从2开始,找到第一个没有被筛的数,把它标记为素数,然后把它的2倍、3倍……筛掉。
复杂度O(nlogn)

改进的埃氏筛法:从2开始,找到第一个没有被筛的数x,把它标记为素数,然后把它的x倍、x+1倍……筛掉。
复杂度O(nloglogn)

线性筛:保证每个数都被它的最小素因子筛掉。
复杂度O(n)

C++写起来大概是这样的:

int mindiv[10000005],tot,prime[10000050];
int main(){
    for(int i=2;i<=10000000;i++){
        if(!mindiv[i]){
            mindiv[i]=i;prime[tot++]=i;
        }
        for(int j=0;prime[j]*i<=10000000;j++){
            mindiv[prime[j]*i]=prime[j];
            if(prime[j]==mindiv[i]) break; //!
        }
    }
    return 0;
}

上述代码求得[1,1000w]的素数,本机Core i3运行用时0.14s,还是很快的。
其中,mindiv[x]保存了x的最小素因子,用它有很多用处(例如分解质因数什么的)。

筛积性函数
积性函数就是指:对于正整数n的一个算术函数 f(n),且当a,b互质时f(ab)=f(a)f(b)。
如:欧拉函数,莫比乌斯函数。
下面以筛欧拉函数为例:
φ(x)表示1-x中与x互质的数的个数。

  • 如果p为质数,φ(p)=p-1。
  • 如果p为质数,φ(p^q)=p^k-p^(k-1)=(p-1)*p^(q-1)。
  • φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数,x是不为0的整数。
  • 若m,n互质,φ(mn)=φ(m)φ(n)。(积性)
  • 当n为奇数时,φ(2n)=φ(n)。

这样我们就可以把所有数分成若干类:

  1. 质数。φ(p)=p-1。
  2. 最小质因子指数不为1。φ(i*p)=φ(i)*p。
  3. 最小质因子指数为1。φ(i*p)=φ(i)*φ(p)。

在筛素数的时候分别处理这三种情况即可。

int mindiv[10000005],tot,prime[10000050],phi[10000050];
int main(){
    for(int i=2;i<=10000000;i++){
        if(!mindiv[i]){
            mindiv[i]=i;prime[tot++]=i;phi[i]=i-1;//1
        }
        for(int j=0;prime[j]*i<=10000000;j++){
            mindiv[prime[j]*i]=prime[j];
            if(prime[j]==mindiv[i]){
                 phi[prime[j]*i]=phi[i]*prime[j] ;break;//2
            }
            phi[prime[j]*i]=phi[i]*(prime[j]-1);//3
        }
    }
    return 0;
}

这样就求出了2-1000w的欧拉函数。
方便快捷。

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框