4.9 KiB
一、题目描述
给定一个正整数 n
,请你求出 1∼n
中质数的个数。
输入格式
共一行,包含整数 n
。
输出格式
共一行,包含一个整数,表示 1∼n
中质数的个数。
数据范围
1≤n≤10^6
输入样例:
8
输出样例:
4
二、埃氏筛法
先去掉2
的倍数,再去掉3
的倍数,再去掉4
的倍数,……依此类推,最后剩下的就是素数。
如求100
以内的素数,我们只要到去掉sqrt(100)
的倍数就可以了,这是因为10
的2
倍已经被2
的倍数去掉了,10
的3
倍已经被3
的倍数去掉了,所以到10
的时候只剩下10
的10
倍以上的素数还存在。
同样的原因,我们在去掉3
的倍数的时候,只要从3
的3倍开始去掉就好了,因为3
的2
倍已经被2
的倍数去掉了。
实现代码
#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
, \large p_1
为最小的素数
由于任意小于 p_1
的质数都不能整除 p_2 \times ... \times p_q
,所以 n
会在遇到primes[j]=p_1
时,也就是 \large i = p_2 \times ...\times p_q
时被筛去。
证毕,总结:就是枚举最小的质数因数
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
枚举到 q_2
时,质数数组是由小到大的,当遍历到 p_1
时,有 i \% p_1 == 0
,此时跳出循环,不会再遍历到后面的 p_2
。
故 n
不会被 p_2
筛去,只会被其最小的素因子 p_1
筛去。
证毕
步骤
- 从
i=2
开始,如果i
还没有被筛掉,则将i
加入至素数列表中 - 遍历当前素数列表
primes[]
,筛去i \times primes[j]
(保证primes[j]*i
不能越界,因为越界了对结果没意义。即i*primes[j]<=n
) - 当遍历到能整除
i
的素数primes[j]
时,筛去i \times primes[j]
,停止对素数列表的遍历 - 重复
2, 3, 4
,直到所有不超过n
的整数都被遍历过
素数列表中的元素即为所求的不超过 n
的所有素数
实现代码
#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;
}