筛法--朴素筛法和埃式筛法和线性筛法-Toy模板网

这篇具有很好参考价值的文章主要介绍了筛法--朴素筛法和埃式筛法和线性筛法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

筛法--朴素筛法和埃式筛法和线性筛法

朴素筛法：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1000010;
int primes[N],cnt;
bool st[N];

void get_primes(int  n){
    
    for(int i=2;i<=n;i++){
         
        if(!st[i])//st==0 代表的是这个数是质数
        {
            primes[cnt++]=i;
        }
        for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }
    }    
}
int main(){
    int n;
    cin>>n;
    get_primes(n);
    
    cout<<cnt<<endl; 
}

这个朴素算法的思路就是，枚举这些数，首先在st数组初始化时，就是已经把这个数组内的值都初始化为0，也就是说都是看成是质数。。。。

然后，如果这个数确实是质数，那么我们就可以把这个数放入我们存质数的数组里面去，然后对质数的个数进行增加，并且，我们把这个质数的倍数（2倍，3倍，4倍。。。。。。）的st都标记为合数（st=1），范围是这个数小于n。。

但是我我们举个例子就可以发现这个朴素的算法有明显的可以优化的地方

让我们看这个代码段

   for(int i=2;i<=n;i++){


 for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }


}

假如这个n是等于12

i=2 倍数有2,4,6,8,10,12 (都会被筛)

i=3 倍数有3，6，9，12 (都会被筛)

i=4 倍数有4，8，12 (都会被筛)

............

从这个中间我们可以看到4，6，8和12是多次被赋值为true的，这个方就会降低算法的效率。。。。这个地方我们就要想办法优化。。。。。

就有一种想法就是：我们不要把所有数的倍数都进行一个赋值，而是有一部分的数进行倍数的赋值------这个数就是质数

也就是说我们对质数的倍数进行赋值----也就是一个埃及人发明的。。---------我们称之为埃式筛法

筛法--朴素筛法和埃式筛法和线性筛法

文章来源地址https://www.toymoban.com/news/detail-466189.html

代码如下：

也就把这个代码段放入循环中：

#include <iostream>
#include <algorithm>
using namespace std;

const int N=1000010;
int primes[N],cnt;
bool st[N];

void get_primes(int  n){
    
    for(int i=2;i<=n;i++){
         
        if(!st[i])//st==0 代表的是这个数是质数
        {
            primes[cnt++]=i;
//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
                for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;

// 这个是被放进来的部分
            
        }
//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
        }
    
    }    
}
int main(){
    int n;
    cin>>n;
    get_primes(n);
    
    cout<<cnt<<endl;
    
    
    
    
}

在上面的埃式筛法中，我们做到了一个优化，但是这个优化也不是很完全：

还是举这个例子来说，n=12时

i=2 倍数有2,4,6,8,10,12 (都会被筛)

i=3 倍数有3，6，9，12 (都会被筛)

i=4 倍数有4，8，12 但是根据算法的思路，我们可以知道，4不是质数所以他的倍数不会被筛，就是这种地方优化了算法的效率。。

然后就是线性筛法，比埃式筛法更快，原因是：做到了每一个数都只被筛一遍-----也就是每一个数只会被他的最小的质因子去筛掉（核心）。

#include <iostream>
#include <algorithm>
using namespace std;

const int N=1000010;
int primes[N],cnt;
bool st[N];

void get_primes(int  n){
    
    for(int i=2;i<=n;i++){//外层循环是枚举所有的数的
  
     if(!st[i]) primes[cnt++]=i;
     for(int j=0;primes[j]<=n/i;j++)
     //j是从小到大枚举所有的质数 
     
     {
         st[primes[j]*i]=true;
         if(i%primes[j]==0) break;
     }
}
}
int main(){
    int n;
    cin>>n;
    get_primes(n);
    
    cout<<cnt<<endl;
        
}

........................................................................................................

引用：(这个地方是没看懂他怎么想的，但是这个例子部分还是很明显易懂的)

②欧拉筛法：任何一个合数都可以写成几个质数相乘的形式，也就是任何一个合数至少有一个最小质因子，而每一个质数的倍数一定不是质数，所以我们可以通过每一个合数的一个最小素因子去筛掉它，并且只筛掉一次，这样就把时间复杂度降到了O(n)。其中就是这条语句起着至关重要的作用：if(i%prime[j]==0)break;为什么呢？举个栗子：假设当前i=9，prime素数表里有2，3，5，7，即先筛掉2*9=18，然后筛掉3*9=27，判断9%3==0，退出当前循环。因为9=3*3，如果继续筛掉5*9，相当于筛3*3*5=3*15，而这个数在i=15时筛掉就可以了。因此，可以用以下的推导证明上面的结论：假设pi是当前i的最小质因子，那么素数表有p1<p2<...<pi<p_i₊₁<...，枚举当前质数表p[j]，j从小到大枚举，直到i%p[j]==0这个条件时，前面所有质数p[j]都是i*p[j]的最小质因子，如果继续枚举下去，即下一个要被筛掉的合数为i*prime[j+1]，因为i中已经含有一个最小质因子prime[j]，设i=k*prime[j]，则i*prime[j+1]=k*prime[j]*prime[j+1]=k'*prime[j]，显然k'>i，k'*prime[j]可以留在后面被筛掉。换句话说，prime[j+1]已不是i*prime[j+1]的最小质因子，i*prime[j+1]必然可以被一个更小的质数prime[j]筛掉，那么k'=i*prime[j+1]/prime[j]=k*prime[j+1]就一定比i大，即下一次i遍历到i=k'时，k'*prime[j]却被其最小素因子prime[j]筛掉，而不是prime[j+1]，这就相当于再筛选了一次（增加了时间复杂度），所以只需将j遍历到i的最小素因子prime[j]就可以了，即保证每一个合数只被其最小质因子筛掉，这样把时间复杂度完美地从O(nloglogn)降到了O(n)。

................................................................................................................

根据自己的分析：

我们用每个合数的最小质因子来进行筛选之所以被称为线性，是因为： 1-n之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,

每一个数都只有一个最小质因子,所以每个数都只会被筛一次,因此线性筛法是线性的。

具体的步骤就是：之前每筛到一个素数j，就将这个素数放入到primes[]中，在每次循环中，从头开始遍历primes[],筛选出的合数就是primes[j]*i,

为了保证每个数只被筛选一次，就要保证每个合数都是被其最小的质因子筛选掉的，所以我们就要找到primes【j】*i的最小质因子，所以我们需分情况讨论：

首先我们知道，primes【j】*i 的最小质因子应该是min（primes【j】,i的最小质因子），也就是说我们需要找到二者中的最小值。。。。。

1.当i%primes[j]不等于0时

此时primes[j]小于i的所有质因子，因为primes[j]是从小到大进行枚举的，如果primes[j]是i中质因子之一，那么就会满足i%primes[j]等于0。

所以我们就可以知道了i的质因子还在后面，还没有加入到我们的primes数组中，所以也就是说，primes【j】就是i*primes【j】的最小质因子

------------所以这种情况下，primes[j]是可以用来筛这个合数 primes【j】*i 的。。。。

2. 当i%primes[j]等于0时