You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

140 lines
4.9 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##[$AcWing$ $868$. 筛质数](https://www.acwing.com/problem/content/description/870/)
### 一、题目描述
给定一个正整数 $n$,请你求出 $1n$ 中质数的个数。
**输入格式**
共一行,包含整数 $n$。
**输出格式**
共一行,包含一个整数,表示 $1n$ 中质数的个数。
**数据范围**
$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)