网站的经典推广方法,海南自贸港跨境电商怎么做,网络运维周报,上海搬家公司收费价目表2021一、算法简介
在数论与编程竞赛中#xff0c;求解 [ 1 , n ] [1,n] [1,n] 范围内的所有质数是常见的基础问题。埃拉托色尼筛法#xff08;Sieve of Eratosthenes#xff09; 是一种古老而高效的算法#xff0c;可以在 O ( n log log n ) O(n \log \log n) O(nlogl…一、算法简介
在数论与编程竞赛中求解 [ 1 , n ] [1,n] [1,n] 范围内的所有质数是常见的基础问题。埃拉托色尼筛法Sieve of Eratosthenes 是一种古老而高效的算法可以在 O ( n log log n ) O(n \log \log n) O(nloglogn) 的时间复杂度内完成这一任务。 二、基本思想
埃氏筛的核心思想是 对于每一个从小到大的质数 p p p将其所有的倍数 2 p , 3 p , 4 p , … 2p, 3p, 4p, \dots 2p,3p,4p,…标记为合数。 最终所有未被标记的数就是质数。 举例说明 设 n 30 n 30 n30初始认为 2 ∼ 30 2\sim 30 2∼30 都是质数。 我们从 2 2 2 开始依次把 4 , 6 , 8 , … 4,6,8,\dots 4,6,8,… 标记为合数 然后处理下一个未被标记的 3 3 3再把 6 , 9 , 12 , … 6,9,12,\dots 6,9,12,… 标记为合数 如此反复直到 n \sqrt{n} n 。 三、代码实现
以下是使用 C 编写的埃氏筛标准模板
#includeiostream
#includevector
using namespace std;const int N 1e5 10; // 设置一个足够大的常数N表示数组大小vectorbool ans(N, true); // 初始化素数表默认所有数都是素数true
vectorint nums; // 用于存储最终得到的所有质数// 筛法主函数获取1到n之间的所有素数
void get(int n)
{ans[0] ans[1] false; // 0 和 1 不是质数直接标记为 false// 使用埃氏筛法从 2 开始依次判断for (int i 2; i n / i; i) // 等价于 i * i n{if (ans[i]) // 如果当前数 i 是质数尚未被筛掉{// 从 i*i 开始而不是 2*i// 因为 i j i*i 范围内的 i 倍数如 2*i, 3*i 等已被更小的质数筛掉了for (int j i * i; j n; j i) // 枚举 i 的所有倍数{ans[j] false; // 将 j 标记为合数}}}// 将所有的质数加入 nums 数组for (int k 2; k n; k){if (ans[k]){nums.push_back(k);}}
}主函数调用如下
int main()
{int n;cin n; // 输入要求筛到的最大范围get(n); // 执行筛法for (auto num : nums){cout num ; // 输出所有质数}return 0;
}四、关键优化说明
1. 为什么从 i * i 开始筛
因为在遍历到质数 i i i 时小于 i i i 的质数已经处理了 2 i , 3 i , . . . , ( i − 1 ) i 2i, 3i, ..., (i-1)i 2i,3i,...,(i−1)i 的倍数。例如 6 2 × 3 6 2 \times 3 62×3 会在处理 2 2 2 时被筛掉 9 3 × 3 9 3 \times 3 93×3 会在处理 3 3 3 时被筛掉。
因此从 i × i i \times i i×i 开始可以减少重复标记提升效率。
2. 循环条件 i n / i
等价于 i * i n这种写法可避免整数溢出建议记住作为一种 防溢出技巧。 五、时间与空间复杂度
时间复杂度 O ( n log log n ) O(n \log \log n) O(nloglogn)非常高效空间复杂度 O ( n ) O(n) O(n)主要用于布尔数组 ans[] 六、样例输入输出
输入
100输出
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97七、适用场景与拓展
快速判断一个数是否为质数配合布尔数组枚举某范围内的所有质数如用于欧拉函数、积性函数计算可拓展为线性筛Euler 筛以避免重复标记时间复杂度为 O ( n ) O(n) O(n) 八、结语
埃拉托色尼筛法是数论的入门利器是多种算法的基础工具。建议熟练掌握并牢记模板结构。同时要理解从 i * i 开始标记的数学依据避免盲记公式。
