题目描述

略

视频地址

【埃式筛法】 https://www.bilibili.com/video/BV1fvCHY6ExV/?share_source=copy_web&vd_source=6a3494b432f4f0cd85b8778d3e41c95f
【欧拉筛法】 https://www.bilibili.com/video/BV1fvCHY6Eya/?share_source=copy_web&vd_source=6a3494b432f4f0cd85b8778d3e41c95f

算法1–埃氏筛法

逻辑：

暂时默认$ 2\sim n $所有数都是质数；（筛法的共性）
遍历$ 2\sim \sqrt{n} $，$i$ 为质数时，将 $i$ 的所有倍数标记为不是质数，即筛掉。

合理性分析：

本算法唯一不太直接的点在于，当遍历到 $i$ 时， $i$ 未被筛掉那么 $i$ 一定是质数吗？是的，如果 $i$ 是合数，则 $i$ 一定可以做质因数分解，即分解为多个质数的乘积，则他一定会被筛掉；例如：$12=2*2*3$ 在遍历到 $2$ 时，就已经将 $12$ 筛掉了。

时间复杂度

约为 $O(n)$

C++ 代码

#include <iostream>
#include <cstring>
#include <math.h>

using namespace std;

bool not_p[1000010];//not_p[i]表示i不是质数，因为bool数组默认是false，即默认都是质数，使用筛法筛去合数

int main()
{
    int n=0,sum=0;
    cin>>n;
    for (int i = 2; i <= n/i; i ++ )
    {
        if(!not_p[i]) //非不是质数，即是质数
        {
            for(int j=i;i*j<=n;j++) not_p[i*j]=true;//如果他是质数，则将他的倍数标记为非质数，即。
                            //为什么在i*i开始标记，举例说明，如果i=5,那么5*2，5*3，5*4都已经被标记了
        }
    }
    for (int i = 2; i <= n; i ++ )
    {
        if(!not_p[i]) sum++;
    }
    cout<<sum;
}

算法2–欧拉筛法

思想：

为了不进行重复的筛去，我们希望每一个合数只被其最小的质因数筛掉，例如，如果使用埃式筛法 $12=2*2*3$ 在 $i=2$ 时，被筛一次，在 $i=3$ 时，又被筛一次，但如果规定了只能由其最小的质因数筛掉的话（即只在 $i=2$ 时，被筛一次），这样就不会重复筛去了

逻辑：

1.暂时默认$ 2\sim n $所有数都是质数；（筛法的共性）
2.遍历$ 2\sim n $ ：
①若 $i$ 是质数，则将 $i$ 整理到一个数组中（这要做单纯是为了方便后续对已确定的质数进行遍历），该数组记为 $primes$ ，遍历 $primes$ ，将 $i*primes[j]$ 筛掉；
②若 $i$ 是合数， $i$ 的最小质因子为 $pi$ 遍历 $primes中<=pi$ 的质数，将i*primes[j]筛掉；

合理性分析:

1.当遍历到 $i$ 时， $i$ 未被筛掉那么 $i$ 一定是质数吗？是的（和上一个差不多）
2.为什么i为合数时，$primes$ 只遍历到 $i$ 的最小质因数？保证每一个合数都被自己的最小质因数筛掉
当 i=3 时， primes={2,3} 遍历 primes ，筛掉 primes[j]*i ，即筛掉 6=primes[0]*3=2*3; 9=primes[1]*3=3*3 ；筛掉的合数算作 primes[j] 的战绩，即2(即 primes[0] )筛掉了6，3(即 primes[1] )筛掉了9。
例如 i=6 ,此时 primes={ 2,3,5 } ，只遍历到2，因为，$6$ 的最小质因数为2，因此，当primes[j]==3时（primes[j]>6的最小质因数2）筛掉18=primes[1]*6=3*6，筛掉18算作3(即primes[1])的战绩，然而18的最小质因数是和6相同的2，然而这个战绩应该是2(即primes[1])，因此我们暂时不筛掉18，应该在 i=9 时筛掉18。

时间复杂度

约为 $O(n)$

C++ 代码

#include <iostream>
#include <cstring>
#include <math.h>

using namespace std;

bool not_p[1000010];//not_p[i]表示i不是质数，因为bool数组默认是false，即默认都是质数，使用筛法筛去合数
int primes[1000010];
int p=0;
int main()
{
    int n=0,sum=0;
    cin>>n;
    for (int i = 2; i <= n; i ++ )
    {
        if(!not_p[i]) //i是质数
        {
            primes[p++]=i;
            for (int j = 0; j < p && primes[j]*i<=n ; j++)
            {
                not_p[primes[j]*i] = true;
            }
        }
        else
        {
            for (int j = 0; j < p && primes[j]*i<=n ; j++)
            {
                not_p[primes[j]*i] = true;
                if (i%primes[j] == 0) break;
            }
        }

    }

    //统计
    for (int i = 2; i <= n; i ++ )
    {
        if(!not_p[i]) sum++;
    }
    cout<<sum;
}