筛质数（埃氏筛＋欧拉筛）

---

题目描述

给定一个正整数 $n$，请你求出 $1\sim n$ 中质数的个数。

输入格式
共一行，包含整数 $n$。

输出格式
共一行，包含一个整数，表示 $1\sim n$ 中质数的个数。

数据范围
$1\le n\le 10^6$

输入样例：

8
1

输出样例：

4
1

---

埃氏筛

埃氏筛的基本思想来源于这么一个事实：
对于任意一个数$num$，它的倍数即$i\times num，i\ge 2$，注定不可能是质数，因为这个倍数的存在说明了$i\times num$有因子$i$，所以可以给这些$i\times num$打上一个标记true，表示它被过滤出质数集合里了，这样做的好处是可以减少循环的操作次数，用st[]数组表示数是否被筛掉，则if(st[i])满足时直接continue就行。
那么筛数的操作如下所示：

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

由于筛数也是比较耗时间的，是否可以优化？再进一步地想，其实只需要对于那些质数进行筛数操作就行了，由于唯一分解定理的可以知道，合数一定会是被它的质因数给筛掉的，而不会造成合数筛掉其成倍数的合数这个重复的操作，所以只在确定了i是质数时才让其进行筛数。

这样做的话时间复杂度是$O(n\times log(logn))$，数学上的证明还可再查相关资料。

C++代码

#include 
#include 
using namespace std;

const int N = 1e6 + 10;

int primes[N];
bool st[N];     //st[i]为true表示这个数被筛掉了；false表示没被筛掉，是质数
int n;

int get_primes(int n){
    int cnt = 0;
    
    for(int i = 2;i <= n;i ++){
        if(st[i])           continue;
        primes[cnt ++] = i;
        for(int j = i + i;j <= n;j += i)        st[j] = true;
    }
    
    return cnt;
}

int main(){
    cin >> n;
    
    int res = get_primes(n);
    
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

线性筛（欧拉筛）

即便埃氏筛的 “只对质数做筛操作” 那一步已经做了很好的优化，但仍然还是存在重复的筛数操作而浪费一定的时间，例如3和7都会对21进行标记。
那么更好的优化方式就是使筛数操作做到不重不漏，那就是线性筛。

线性筛来源于这样一个事实：任何一个合数，只需要利用它的最小质因数筛掉它就可以了。就像上述例子中21只需要被3筛了就行了，再或是对于55，只需要5的时候就筛掉。
不同的是，线性筛要对每个数都进行一遍筛数操作。

这样优化后的复杂度就变为了$O(n)$，数学上的证明还可再查相关资料。

更具体的解析可以看这篇：AcWing 868. 筛质数。

C++代码

#include 
#include 
using namespace std;

const int N = 1e6 + 10;

int primes[N];
bool st[N];     //st[i]为true表示这个数被筛掉了；false表示没被筛掉，是质数
int n;

int get_primes(int n){
    int cnt = 0;
    
    for(int i = 2;i <= n;i ++){
        if(!st[i])      primes[cnt ++] = i;
        
        //下面几步使保证每一个数i都被且仅被其最小的质因数筛掉
        for(int j = 0;primes[j] <= n / i;j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)      break;		//因为 primes[j] 是从小到大枚举的，所以如果存在 i % primes[j] == 0 就说明 primes[j] 已经是 i 的最小质因子了）
        }
    }
    
    return cnt;
}

int main(){
    cin >> n;
    
    int res = get_primes(n);
    
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34