python/TangDou/AcWing/Prime/868.md

##[$AcWing$ $868$. 筛质数](https://www.acwing.com/problem/content/description/870/)

### 一、题目描述
给定一个正整数 $n$，请你求出 $1∼n$ 中质数的个数。

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

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

**数据范围**
$1≤n≤10^6$

**输入样例：**
```cpp {.line-numbers}
8
```

**输出样例：**
```cpp {.line-numbers}
4
```

### 二、埃氏筛法

**[原理解析](https://blog.csdn.net/weixin_45378171/article/details/96422556)**


先去掉$2$的倍数，再去掉$3$的倍数，再去掉$4$的倍数，……依此类推，最后剩下的就是素数。

如求$100$以内的素数，我们只要到去掉$sqrt(100)$的倍数就可以了，这是因为$10$的$2$倍已经被$2$的倍数去掉了，$10$的$3$倍已经被$3$的倍数去掉了，所以到$10$的时候只剩下$10$的$10$倍以上的素数还存在。

同样的原因，我们在去掉$3$的倍数的时候，只要从$3$的3倍开始去掉就好了，因为$3$的$2$倍已经被$2$的倍数去掉了。

![QQ截图20210225151603.png](https://cdn.acwing.com/media/article/image/2021/02/25/64630_56cdc5c977-QQ截图20210225151603.png) 

#### 实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
int st[N];          // st[x]存储x是否被筛掉
// 埃拉筛
void get_primes(int n) {
    for (int i = 2; i <= n; i++)
        if (!st[i]) {
            primes[cnt++] = i; // 记录素数
            for (int j = 2 * i; j <= n; j += i)
                st[j] = 1; // 成倍数的标识
        }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    printf("%d\n", cnt);
    return 0;
}
```

### 三、欧拉筛

* 不用每次筛去后剩下的能确定是素数中最大的数作为操作主体(在埃拉托色尼筛法中用$2$，$3$，$5$…)，而是用已经晒出来的质数数组中的数作为操作主体

* 核心思想：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。


#### 原理

##### 1、每个合数都会被筛去
**证明：**
若 $n$ 为合数，设其质因子分解为 $$\LARGE n = p_1  \times p_2\times ...\times p_q$$，其中$\large p_i$可以等于$\large p_j$ , <font color='red' size=4><b>$\large p_1$ 为最小的素数</b></font>

由于任意小于 $p_1$ 的质数都不能整除 $p_2 \times ... \times p_q$，所以 $n$ 会在遇到$primes[j]=p_1$时，也就是 $\large i = p_2 \times ...\times p_q$ 时被筛去。

**证毕**,<font color='red' size=4><b>总结：就是枚举最小的质数因数</b></font>

##### 2、每个合数只会被筛去$1$次

**反证法：**
设合数 $n$ 即被 **质数**$\large p_1$ 筛去，也被 **质数**$\large p_{2}$ 筛去。那么有 $\large n = q_1 \times p_1 = q_2 \times p_2$，其中 $p_1$ 和 $p_2$ 均是 $n$ 的素因子。

不妨设 $\large p_1 < p_2$，则有$q_1>q_2$,且$p_1 和 p_2$ 互素，故有 $\large p_1 | q_2$,也就是$\large q_2 \% p_1=0$

当$i$ <font color='blue' size=4><b>枚举到</b></font> $q_2$ 时，质数数组是由小到大的，当遍历到 $p_1$ 时,有 $i \% p_1 == 0$，此时跳出循环，不会再遍历到后面的 $p_2$。

故 $n$ 不会被 $p_2$ 筛去，只会被其最小的素因子 $p_1$ 筛去。

**证毕**


#### 步骤

* 从 $i=2$ 开始，如果 $i$ 还没有被筛掉，则将 $i$ 加入至素数列表中
*  <font color='red' size=4><b>遍历当前素数列表$primes[]$</b></font>，<font color='blue' size=4><b>筛去 $i \times primes[j]$</b></font> 
  (保证$primes[j]*i$不能越界，因为越界了对结果没意义。即$i*primes[j]<=n$)
  * 当遍历到能整除 $i$ 的素数 $primes[j]$ 时，筛去 $i \times primes[j]$，<font color='red' size=4><b>停止对素数列表的遍历</b></font>
* 重复 $2, 3, 4$，直到所有不超过 $n$ 的整数都被遍历过

素数列表中的元素即为所求的不超过 $n$ 的所有素数


#### 实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
int st[N];          // st[x]存储x是否被筛掉

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) { // 捋着质数数组来
            st[primes[j] * i] = 1;                 // 质数因子的i倍被干掉
            if (i % primes[j] == 0) break;         // 只被它的最小质因子筛选一次
        }
    }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    printf("%d\n", cnt);
    return 0;
}
```

### 五、练习题
[洛谷 $P3912$ 素数个数](https://www.luogu.com.cn/problem/P3912)