质数的两种常用判断方法——埃氏筛法和欧拉筛法

1.埃氏筛法:时间复杂度是O(nlognlogn)，打表把一定范围内的质数都记录在数组里所以空间复杂度较高。具体的实现是通过两个数组一个prime记录当前范围的质数序号，另一个isprime判断是否是素数，将isprime初始化为1，从i=2开始遍历标记所有i的倍数的数的isprime为零。

代码:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 #define mem(s,n) memset(s,n,sizeof s);
 8 typedef long long ll;
 9 const int maxn=9e2+1;
10 const int Inf=0x7f7f7f7f;
11 bool isPrime[maxn];
12 int primes[maxn];
13 //当然，当数据太大导致普通数组存不下的时候，可以采用stl里的vector来存
14 int cnt;
15 void judgePri()
16 {
17     mem(isPrime, 1);
18     cnt = 0;
19     isPrime[1] = 0;//1特殊处理 
20     for (int i = 2; i < maxn; i++) 
21     {
22         if (isPrime[i] == 1)
23         {
24             primes[cnt++] = i;
25             for (int j = i; j < maxn; j += i) //标记i在N范围内的所有倍数
26             {
27                 isPrime[j] = 0;
28             }
29         }
30     }
31 }
32  
33 int main(void)
34 {
35     judgePri();
36     for (int i = 0; i < cnt; i++)
37     {   
38         if(i%9==0) cout<<endl;
39         printf("%d ", primes[i]);
40     }
41     return 0;
42 }

View Code

然而我们会发现一个问题就是有重复标记的情况，举个例子6第一次i=2时就已经标记了但是i=3又遍历了一次，这样其实就是浪费操作了，所以引入一种改进算法欧拉算法。

2.欧拉算法：时间复杂度O(n)，主体思路还是建立在埃氏筛法的基础上，对其重复标记进行了优化。我们很容易想到只用合数中的一个因数筛选掉这个合数。思路实现——利用前面求得的质数，从小到大遍历如果i被prime[j]整除那么跳出循环，同时也把i*prime[j]遍历了标记成合数。(具体实现见代码）

代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
#define mem(s,n) memset(s,n,sizeof s);
typedef long long ll;
const int maxn=9e2+1;
const int Inf=0x7f7f7f7f;
bool isPrime[maxn];
int primes[maxn];
int cnt;
void judgePri() 
{
    int temp;
    mem(isPrime, 1);
    cnt = 0;
    isPrime[1] = 0;
    for (int i = 2; i < maxn; i++)
    {
        if (isPrime[i] == 1)
        primes[cnt++] = i;
        //优化
        for (int j = 0; j < cnt && (temp = i * primes[j]) < maxn; j++) //找i之前的所有质数 
        {
            isPrime[temp] = 0;//i * primes[j]肯定是合数，先标记掉 
            if (i % primes[j] == 0)//关键，每次整除一个最小的质数将会跳出循环，所以每个数字，只会被最小的质数筛一次 
            {
                break;
            }
        }
        //优化 
    }
}
 
int main(void)
{
    judgePri();
    for (int i = 0; i < cnt; i++)
    {   
        if(i%9==0) cout<<endl;
        printf("%d ", primes[i]);
    }
    return 0;
}

View Code

3.常用板子：

 1 int  f[maxn];//f[i]表示i的因子个数
 2 int pri[maxn];
 3 int notpri[maxn];
 4 int prime[maxn];
 5 ll p[maxn]; // p[i] 表示 i由几个素因子组成如 p[6]=2 2*3 p[8]=3 2*2*2
 6 void init(){
 7     now=0;f[1]=1;
 8     notpri[0]=notpri[1]=1;
 9     for(int i=2;i<=maxn-1;i++){
10         if(!notpri[i])pri[++now]=i,f[i]=2,p[i]=1;
11         for(int j=1;j<=now&&pri[j]*i<=maxn-1;j++){
12             notpri[i*pri[j]]=1;
13             if(i%pri[j]==0){//有pri[j]作为质因子时
14                 f[i*pri[j]]=f[i]*(p[i]+2)/(p[i]+1);
15                 p[i*pri[j]]=p[i]+1ll;
16                 break;
17             }
18             f[i*pri[j]]=f[i]*f[pri[j]];//互质则直接乘
19             p[i*pri[j]]=p[i]+1ll; 
20         }
21     }
22     // rep(i,1,10) {
23     //     cout<<i<<" "<<p[i]<<endl;
24     // }
25     rep(i,1,maxn-1) pre[i]=pre[i-1]+p[i];
26 }