|
|
##[$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$的倍数去掉了。
|
|
|
|
|
|

|
|
|
|
|
|
#### 实现代码
|
|
|
```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)
|