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;
}