【基本算法】欧拉线性质数筛

目录

• 为什么要用欧拉线性质数筛？
• 大体思路
• 模板代码

  为什么要用欧拉线性质数筛？

  以下代码是一个简单的质数筛

  #include#define ll long long
  using namespace std;
  int n,Q,k,prime[10000007],cnt,vis[100000008];
  void init(){vis[0]=vis[1]=1;
  	for(int i=2;i<=n;i++)
  	{if(vis[i]==0) 
  		{prime[++cnt]=i;
  			for(int j=i+i;j<=n;j+=i) vis[j]=1;
  		}
  	}
  	return ;
  }
  int main(){scanf("%d%d",&n,&Q);
  	init();
  	for(int i=1;i<=Q;i++)
  	{scanf("%d",&k);
  		printf("%d\n",prime[k]);
  	}
  	return 0;
  }
  

  相信大家都会写这个埃氏筛吧

  但是众所周知，这个代码的时间复杂度大概是 O ( n ∗ √ n ) O(n*√n) O(n∗√n)

  但凡数据范围大一点，如10⁷，埃氏筛就要超时了。

  那是哪里多算了很多次呢？

  显然，当一个数有多个因数时，它会被多个因数筛掉

  所以，我们就想要找到一种只会被一个质因数筛掉的算法

  大体思路

  既然是只让一个质因数筛掉它，那么为了方便，肯定是被最大质因数或最小质因数筛掉

  我们考虑被最小质因数筛掉的情况

  我们先假设要被筛掉的数是 6 6 6（ x x x ）

  已有的质数 2 2 2 3 3 3 5 5 5 （ p r i m e [ s ] prime[s] prime[s] ）

  那么我们肯定希望用 2 2 2 筛掉它，而不是 3 3 3

  怎么处理呢？

  我们可以枚举到一个小于 x x x 的数 k k k 时，拿 k k k 乘以已知的质数

  有人可能会问：“这和埃氏筛有什么区别吗？”

  区别在于，当 k k k 是一个质数 p r i m e [ s ] prime[s] prime[s] 的倍数时，直接退出(不用 k k k 乘更大的数了)

  为什么可以这样做？

  ∵ ∵ ∵ k = y ∗ p r i m e [ s ] k=y*prime[s] k=y∗prime[s] (即 x x x 为) ( s < t ) (s

  ∴ ∴ ∴ k ∗ p r i m e [ t ] = y ∗ p r i m e [ s ] ∗ p r i m e [ t ] = x k*prime[t]=y*prime[s]*prime[t]=x k∗prime[t]=y∗prime[s]∗prime[t]=x

  又 ∵ ∵ ∵ 遇到 k k k 的因数就 b r e a k break break，所以 p r i m e [ s ] prime[s] prime[s] 为 x x x 的最小质因数

  ∴在未来 x x x 为 p r i m e [ t ] ∗ k prime[t]*k prime[t]∗k 时，一定会被 p r i m e [ s ] prime[s] prime[s] 筛掉

  所以 x x x 一定只会被最小质因数筛掉

  模板代码

  #include#define ll long long
  using namespace std;
  int n,Q,k,prime[10000007],cnt,vis[100000008];
  void init(){ /*让k的最小的质因数筛掉他*/
  	vis[0]=vis[1]=1;
  	for(int i=2;i<=n;i++)
  	{if(vis[i]==0) prime[++cnt]=i;
  		for(int j=1;j<=cnt && prime[j]*i<=n;j++)
  		{vis[i*prime[j]]=1;
  			if(i%prime[j]==0) break; 
  			/*
  				例如：  i=6
  					prime:2 3 5
  				∵i=k*prime[s]; (sscanf("%d%d",&n,&Q);
  	init();
  	for(int i=1;i<=Q;i++)
  	{scanf("%d",&k);
  		printf("%d\n",prime[k]);
  	}
  	return 0;
  }