#sx001. 埃氏筛法(埃拉托斯特尼筛法)
埃氏筛法(埃拉托斯特尼筛法)
埃氏筛法(埃拉托斯特尼筛法)
题目描述
给定一个正整数 n,请使用埃氏筛法(Sieve of Eratosthenes) 找出 2 到 n 之间的所有质数,并按从小到大顺序输出。
算法概念
埃氏筛法是一种简单且古老的筛法,用于在给定范围内找出所有质数。其基本思想是从 2 开始,将每个质数的倍数标记为合数,未被标记的数即为质数。该算法的时间复杂度为 O(n log log n),在 n 较大时依然高效,是数论中最基础且常用的质数筛法之一。
算法原理与步骤
- 创建一个长度为 n+1 的标记数组 isComposite(或 a),下标 i 表示数字 i,元素值 0 表示 i 是质数,1 表示 i 是合数。初始时所有元素均为 0,即默认所有数都是质数。
- 从 2 开始遍历到 sqrt(n)(即 i*i ≤ n),如果当前数 i 未被标记(isComposite[i] == 0),则 i 是质数。
- 将 i 的倍数(从 i开始,步长为 i)全部标记为合数(isComposite[j] = 1)。优化:从 i*i 开始标记,因为小于 i*i 的倍数已经被更小的质数标记过。
- 遍历完成后,数组中仍为 0 的下标(从 2 到 n)即为所有质数。
- 按顺序输出这些质数。
输入格式
一行一个正整数 n。
输出格式
一行,输出从 2 到 n 中的所有质数,相邻质数用空格隔开。
输入输出样例
20
2 3 5 7 11 13 17 19
数据规模与约定
2 ≤ n ≤ 10^6
时间限制:1 秒(埃氏筛法 O(n log log n),n=10^6 时约 10^6 次操作,可轻松通过)
内存限制:256 MB(标记数组约 4 MB,满足要求)
提示
代码提示:
cin >> n;
// 数组下标代表要筛查的数,元素值 0 表示质数,1 表示合数
int isComposite[1000001] = {0};
// 埃氏筛法
for (int i = 2; i * i <= n; i++) {
if (isComposite[i] == 0) { // i 是质数
// TODO: 将 i 的倍数从 i*i 开始标记为合数
// 提示:for (int j = ?; j <= n; ?) isComposite[j] = 1;
}
}
// 输出所有质数
for (int i = 2; i <= n; i++) {
// TODO: 如果 isComposite[i] == 0,则输出 i
}
运用提示:
埃氏筛法的核心是“标记合数”,从每个质数 i 的平方开始标记,可以避免重复标记。
数组大小需至少为 n+1,本题 n ≤ 10^6,故开 1000001 足够。
注意循环边界 i*i ≤ n,防止 i*i 溢出 int(可用 i <= sqrt(n) 或强制类型转换),但 i 最大为 1000,不会溢出。
若需要输出个数,可以额外统计;但本题只要求输出质数本身。
埃氏筛法是最基础的质数筛法,在此之上可学习欧拉筛(线性筛)以进一步优化。