精华内容
下载资源
问答
  • 线性筛

    2020-07-21 23:10:39
    目录参考视频素数筛[P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)朴素筛埃氏筛-Eratosthenes 筛法 (埃拉托斯特尼筛法)Euler 筛法 (欧拉筛法)线性筛求欧拉函数预备知识代码线性筛求...

    参考视频

    线性筛是用来求特定函数f(x)的一种方法

    素数筛

    P3383 【模板】线性筛素数

    • 问题:求小于等于 n 有多少个素数分别是什么

    朴素筛

    • 暴力枚举
    int is_prime(int n)
    {
    	if(n==1)return 0;
    	for(int i=2;i<=sqrt(n);i++)
    	if(n%i==0)return 0;
    	return 1;
    }
    

    埃氏筛-Eratosthenes 筛法 (埃拉托斯特尼筛法)

    • 核心:从头开始,找到一个素数,把它的倍数全部标记(相当于筛掉)
    
    int Eratosthenes(int n)
    {
    	int cnt=0;
    	for(int i=0;i<=n;i++)isprime[i]=1;
    	isprime[0]=isprime[1]=0;
    	for(int i=2;i<=n;i++)
    	{
    		if(isprime[i])prime[cnt++]=i;
    		for(int j=i*2;j<=n;j+=i)isprime[j]=0;
    	} 
    	return cnt;
    }
    

    Euler 筛法 (欧拉筛法)

    • 思路:对埃氏筛的一种优化
      例如:
      6=2 * 3
      用埃氏筛时,筛除6的时候,i=2时筛了一次,i=3时又筛了一次,出现了重复筛的现象
    • 任何合数都能写成一个素数乘一个数,所以任何合数都有一个最小的质因数,用这个最小质因数来判断什么时候不用继续筛下去,即i (当前数) >最小质因数
    • 怎么判断?
      if(i%prime[j]==0) 则 i=k * prime[j]
      如果j继续++的话,某合数= i * prine[j+1] = prime[j] * k * prime[j+1]
      此时prime[i+1]就不时最小素质数
      该合数=prime[j] * ( k * prime[j+1] )
      所以i=k*prme[j+1]就会重复,此处用break可以提高代码
      效率
    
    int Euler(int n)
    {
    	vis[0]=vis[1]=1;
    	int cnt=0;
    	for(int i=2;i<=n;i++)
    	{
    		if(!vis[i])prime[cnt++]=i;
    		for(int j=0;j<cnt&&prime[j]*i<=n;j++)
    		{
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0)break;
    		}
    	}
    	return cnt;
    }
    

    线性筛求欧拉函数

    预备知识

    • 欧拉函数:对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)
    • 积性函数:对于任意互质的整数a和b有性质f(a*b)=f(a)*f(b)的数论函数。
      (这里的)欧拉函数和 (下面的) 莫比乌斯函数都是积性函数
      if(i%prime[j]!=0) phi[i*prime[j]] = phi[i]*phi[prime[j]]
    • 定理gcd(a,b)==1 则 gcd(a,a+b)==1
      1到i中有x个数与i互质 则 i+1到2i中也有x个数与i互质
      if(i%prime[j]==0) phi[i*prime[j]] = phi[i]*prime[j];

    代码

    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    const int N=5e7;
    int vis[N],phi[N],prime[N];
    //欧拉函数是小于或等于n的正整数中与n互质的数的数目
    void phi_table(int n)
    {
    	phi[1]=1;int cnt=0;
    	for(int i=2;i<=n;i++)
    	{
    		if(!vis[i])
    		{
    			prime[cnt++]=i;
    			phi[i]=i-1;
    		}
    		for(int j=0;j<cnt&&prime[j]*i<=n;j++)
    		{
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0)
    			{
    				phi[i*prime[j]]=phi[i]*prime[j];
    				break;
    			}
    			else phi[i*prime[j]]=phi[i]*(prime[j]-1);//phi[i*prime[j]]=phi[i]*phi[prime[j]]
    		}
    	}
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	phi_table(n);
    	for(int i=1;i<=n;i++)printf("%d  ",phi[i]);
    	printf("\n");
    	return 0;
    }
    

    线性筛求莫比乌斯函数

    • 莫比乌斯函数:x=p1k1p2k2
      f(x)=0 存在ki>=2
      否则 f(x)=(-1)n n为ki=1的个数即x的质因数的个数
    • 代码
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    const int N=5e7;
    int vis[N],mo[N],prime[N];
    void mobius(int n)
    {
    	mo[1]=1;int cnt=0;
    	for(int i=2;i<=n;i++)
    	{
    		if(!vis[i])
    		{
    			prime[cnt++]=i;
    			mo[i]=-1;
    		}
    		for(int j=0;j<cnt&&prime[j]*i<=n;j++)
    		{
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0)
    			{
    				mo[i*prime[j]]=0;
    				break;
    			}
    			else mo[i*prime[j]]=-mo[i];
    		}
    	}
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	mobius(n);
    	for(int i=1;i<=n;i++)printf("%d  ",mo[i]);
    	printf("\n");
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,478
精华内容 1,791
关键字:

线性筛