#sx001. 埃氏筛法(埃拉托斯特尼筛法)

埃氏筛法(埃拉托斯特尼筛法)

埃氏筛法(埃拉托斯特尼筛法)

题目描述

​ 给定一个正整数 n,请使用埃氏筛法(Sieve of Eratosthenes) 找出 2 到 n 之间的所有质数,并按从小到大顺序输出。

算法概念

​ 埃氏筛法是一种简单且古老的筛法,用于在给定范围内找出所有质数。其基本思想是从 2 开始,将每个质数的倍数标记为合数,未被标记的数即为质数。该算法的时间复杂度为 O(n log log n),在 n 较大时依然高效,是数论中最基础且常用的质数筛法之一。

算法原理与步骤

  1. 创建一个长度为 n+1 的标记数组 isComposite(或 a),下标 i 表示数字 i,元素值 0 表示 i 是质数,1 表示 i 是合数。初始时所有元素均为 0,即默认所有数都是质数。
  2. 从 2 开始遍历到 sqrt(n)(即 i*i ≤ n),如果当前数 i 未被标记(isComposite[i] == 0),则 i 是质数。
  3. 将 i 的倍数(从 i开始,步长为 i)全部标记为合数(isComposite[j] = 1)。优化:从 i*i 开始标记,因为小于 i*i 的倍数已经被更小的质数标记过。
  4. 遍历完成后,数组中仍为 0 的下标(从 2 到 n)即为所有质数。
  5. 按顺序输出这些质数。

输入格式

​ 一行一个正整数 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,不会溢出。

​ 若需要输出个数,可以额外统计;但本题只要求输出质数本身。

​ 埃氏筛法是最基础的质数筛法,在此之上可学习欧拉筛(线性筛)以进一步优化。