当前位置：首页 > news >正文

算法刷题笔记筛质数（详细注释的C++实现，同时包含朴素筛法、埃氏筛法和线性筛法详细介绍）

news 来源：原创 2024/9/20 9:28:33

文章目录

- 题目描述
- 基本思路
- - 朴素筛法
  - 埃氏筛法
  - 线性筛法
- 实现代码
- 后记

题目描述

给定一个正整数n，请你求出1∼n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1∼n中质数的个数。

数据范围

1 ≤ n ≤ 10^6

基本思路

朴素筛法

基本步骤：
- 由于已知1不是质数，因此可以忽略。
- 从2开始，按照从小到大的顺序遍历所有的数字。如果某个数字被标记为了合数则跳过；如果该数组没有被标记为合数，则找出该数字的倍数，并将这些倍数标记为合数。初始情况下所有数字都未被标记为合数。
- 完成遍历后，输出未被标记为合数的整数的个数即可。
算法原理：如果对于某一个数字p，从2到p-1的遍历过程中都没有将该数字标记为合数，则说明从2到p-1都不存在该数字的因数，所以该数字一定是一个质数。
时间复杂度分析：由于存在n个数字，因此需要进行n轮循环，每轮循环内部的循环分别要遍历n\2、n\3、…、n\n次，总体时间复杂度为O(n*(n/2+n/3+...n/n))，根据调和级数求和的相关知识，可以判定时间复杂度为O(nlnn)，等价于O(nlogn)。

埃氏筛法

算法历史：该算法由古希腊数学家埃拉托斯特尼提出。
朴素筛法存在的效率问题：朴素筛法中，其实并不需要将所有数字的倍数都删除，而是只需要删除质数的倍数即可，这样可以进一步提高算法的执行效率。
基本步骤：
- 初始条件下，默认从2到n的所有数字都是素数。
- 和朴素筛法一样，标记2的所有倍数为合数。
- 下一轮迭代从下一个质数（即未被标记为合数的数字）开始，而不是当前数字紧邻的下一个数字。
质数定理：在1到n之间，只存在n/lnn个质数。
时间复杂度：相对于朴素筛法，该算法并不需要进行n轮循环。根据质数定理，该算法的循环轮数从n降低到了n/lnn，所以算法的时间复杂度也变为了O(nlnn/n)，即O(n)。然而，这个时间复杂度其实并不准确，准确的时间复杂度是O(nloglogn)，因此当数据范围（也就是n）很大时，该算法的执行效率仍然不是特别令人满意。

线性筛法

埃氏筛法存在的效率问题：埃氏筛法虽然相较于朴素筛法减少了外层循环的次数，但是在标记合数的部分仍然存在冗余，即对于同样一个合数，可能会对其进行多次考虑和标记，这样的冗余操作就会占用大量的时间。
基本思想：任何一个合数都可以写为多个质因子相乘的形式，但是每一个合数都存在一个最小质因子，因此通过最小质因子来标记一个合数，就一定不会存在冗余。这种情况下，每一个合数都只会被其最小质因子给标记为合数。
基本步骤：
- 该算法基于朴素算法，同样需要遍历从2到n的所有数字（而不是质数）。但是区别在于对于找到的每个数字，标记合数的方式不太一样，并不是基于简单的倍数标记。
- 该算法对于迭代过程中的每一个数字，首先判定其是不是质数，如果是质数（即没有标记为合数）则将其放入质数列表中，然后将该数字按照从小到大的顺序与质数列表中的每一个质数pi相乘，相乘的结果需要保证在在区间[1,n]内。乘积结果一定是以pi为最小质因子得到的合数，也就是说每一个合数都只会被标记一次。
时间复杂度：相较于埃氏筛法的O(nloglogn)的时间复杂度，线性筛法的时间复杂度稳定降低到了O(n)，这一降低在数据范围很大的时候尤为明显。
其他说明：线性筛法也被称为欧拉筛法。

实现代码

#include <cstdio>
#include <vector>
using namespace std;// 【变量定义】整数的数据范围
int n;
// 【变量定义】记录质数的个数
int result;
// 【辅助常量定义】数据范围的上限
const int N = 1e6 + 10;
// 【变量定义】记录数字是否为合数的布尔数组（初始情况下所有整数都默认为质数）
bool is_composite[N];
// 【变量定义】用于按照从小到大的顺序记录质数的向量
vector<int> primes;// 【函数定义】用于求出从1到n之间的质数的个数的函数（基于线性筛法）
int Prime_count(int n)
{// 从2开始遍历所有的数字for(int i = 2; i <= n; ++ i){// 如果当前的数字是质数，则将其放入质数列表中if(is_composite[i] == false) primes.push_back(i);// 在指定的范围内，将当前的数字与质数列表中的质数逐一相乘，标记乘积结果是合数for(int j = 0; j < primes.size() && primes[j] <= n / i; ++ j){is_composite[i * primes[j]] = true;// 如果当前质数列表中正遍历到的质数是当前数字的因子，则该质数一定是当前数字的最小质因子// 因为primes[j]是i的因子，因此质数列表中更大的质数乘i的结果都可以质因数分解出prime[j]，形成重复标记，因此需要提前结束循环避免if(i % primes[j] == 0) break;}}// 将质数列表中的数字个数返回return primes.size();
}int main(void)
{// 【变量输入】输入需要进行质数筛选的数据范围上限scanf("%d", &n);// 【获取结果】通过自定义的函数获取从1到n的整数中质数的个数result = Prime_count(n);// 【结果输出】输出1到n之间的质数的个数printf("%d", result);return 0;
}