欧拉筛法

a 今天试着写一发欧拉筛 # 啥子是欧拉筛？ 欧拉筛，是欧拉的筛法 ~~我也不知道是谁的，应该是吧~~。 ### 它的思想是：每个合数只被自己的最小质因数筛一次，以此达到时间复杂度O(n)的效果。 为什么可以实现，以及为什么要这样呢？ 我们来看：假设有合数h=x * y，（x为质数），若y为质数，则我们可知，h的最小质因数在x、y之中，若y为合数，y总可以分成数个质数相乘的形式，则最小质因数在x、以及这些质数之中，同时我们也可以得到信息：h很可能可以分成多种形式，如 x乘y，c乘d等等，所以 #### 普通的筛法会将一个合数多次筛去，即重复计算 故我们使用欧拉筛 ## 那么如何实现？ ------------ ```cpp #include<bits/stdc++.h> #define maxb 1000000 using namespace std; bool pan[100000100];//判断是不是素数的数组 int prime[1000000],num,n,m;//prime数组存得到的质数，从小到大存 void in(){//num是目前素数个数 cin>>n>>m; } void su(){ memset(pan,true,sizeof(pan)); pan[0]=false; pan[1]=false; for(int i=2;i<=n;i++){ if(pan[i]){//如果是素数，把它存到数组里，同时个数+1 prime[++num]=i; } for(int j=1;j<=num;j++){ pan[i*prime[j]]=false; if(i%prime[j]==0){//这一句是整个算法的核心，下面会说到 break; } } } } int main(){ // freopen("3.txt","r",stdin); in(); su(); } ``` 好的，让我们来pick下这一句 ```cpp if(i%prime[j]==0){ break; } ``` 正是这一句的存在，保证了每个合数只被筛一遍。 ### 因为：prime数组中的质数是从小到大存的，如果i%prime[j]==0,说明这时prime[j]刚好是i的因子，也是i的最小质因数，此时得到的合数h=i乘prime[j]，依旧是被自己的最小质因数筛去，如果没有这一句，会出现：h1=i乘 prime[j2]，且prime[j2]不是h1的最小质因数 ， 这种情况。那么就会产生重复计算。 举个栗子： 我们要筛掉数 63 当i=21，prime[j]=3时，63被筛掉 而 i=9，prime[j]=7时则不会，因为i=9时，这个循环中，循环到prime[j]=3时，就会break出来，根本不会再继续，故这种情况根本不会出现 贴个图加强理解  最后补一句： #### 欧拉筛虽快，但需要空间复杂度较高，容易RE 差不多了，溜~~~