筛法总结

发表于 | 分类于

筛法总结

欧拉筛法

埃氏筛法比较弱，复杂度太高，就不介绍了，在此之上有优化过的欧拉筛法，复杂度是线性的，所以也叫线性筛，可以在$O(n)$处理出$[2,n]$的质数表。

具体的优化就在于每个数都只被其最小质因子筛去。

code

1
2
3
4
5
6
7
8
9
10
11
for(int i=2;i<=n;i++)
    {
        if(mark[i]==false)//mark[i]==false=>是质数
            prime[num++]=i; //prime记录下质数表
        for(int j=0;j<num&&prime[j]*i<=n;j++)
        {
            mark[prime[j]*i]=true;
            if(i%prime[j]==0)
                break;//优化
        }
    }

欧拉函数$\varphi()$

积性函数

如果一个数论函数(定义没什么用，在此不叙述)$f(x)$满足
$$f(xy)=f(x)×f(y),x,y\in prime$$
那么$f(x)$就称为积性函数

特别的 如果对于任意$x,y$都有上式成立，则$f(x)$为完全积性函数。

欧拉函数是一个积性函数

积性函数可以用线性筛快速求

根据其性质直接求即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void calphi()
{
    for(int i=2;i<=1e6+1;i++)
        {
            if(mark[i]==false)
                prime[cnt++]=i,phi[i]=i-1;
            for(int j=0;j<cnt&&i*prime[j]<=1e6+1;j++)
            {
                mark[i*prime[j]]=true;
                if(i%prime[j]==0)
                {
                    phi[i*prime[j]]=phi[i]*prime[j];
                    break;
                }
                else
                    phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
	}

莫比乌斯函数

不用说，这也是个积性函数，求法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
mu[1]=1;/mu[1]=1根据定义
       int tot=0;
       for(int i=2;i<=50000;i++)
       {
           if (!mark[i])
           {
               p[++tot]=i;
               mu[i]=-1;
           }
           for(int j=1;j<=tot;j++)
           {
               if (i*p[j]>50000) break;
               mark[i*p[j]]=1;
               if (i%p[j]==0)
               {
                   mu[i*p[j]]=0;
                   break;
               }
               else mu[i*p[j]]=-mu[i];
           }
       }