C++ 素数筛法：埃氏筛与线性筛原理及实现

C++ 素数筛法：埃氏筛与线性筛原理及实现

概述

在数字王国里，寻找素数是一项基础任务。对于大范围数据，逐个判断效率低下。本文介绍两种高效筛选算法：埃氏筛（Eratosthenes Sieve）和线性筛（Euler Sieve）。

一、埃氏筛法

1. 核心思想

每发现一个素数，就把它的倍数全部划掉。这样剩下的就都是素数。

2. 步骤示例

以 1~30 为例：

1. 初始化所有数为素数。
2. 从 2 开始，将 2 的倍数划掉。
3. 找到下一个未被划掉的数（3），将其倍数划掉。
4. 重复直到处理完 √n。

3. 优化说明

• 只需筛到 √n：若 n 是合数，必有因子 ≤ √n。
• 从 i*i 开始：小于 i*i 的倍数已被更小的质因数筛过。

4. 时间复杂度

O(n log log n)

5. 代码模板

#include <iostream>
using namespace std;
const int N = 1000000;
bool isPrime[N];

int main() {
    int n;
    cin >> n;
    for(int i=2; i<=n; i++) isPrime[i] = true;
    for(int i=2; i*i<=n; i++) {
        if(isPrime[i]) {
            for(int j=i*i; j<=n; j+=i) isPrime[j] = false;
        }
    }
    for(int i=2; i<=n; i++) {
        if(isPrime[i]) cout << i << " ";
    }
    return 0;
}

二、线性筛法

1. 核心思想

每个合数 = 最小质因数 × 另一个数。只用最小质因数来筛掉它，保证每个合数只被删一次。

2. 关键逻辑

• 维护素数表 prime[]。
• 遍历 i，若 i 是素数则加入表。
• 用 i 乘以素数表中的数生成合数。
• 若 i % prime[j] == 0，则停止（保证 prime[j] 是 i 的最小质因数）。

3. 时间复杂度

O(n)，真正的线性时间。

4. 代码模板

#include <iostream>
using namespace std;
const int N = 1000000;
int prime[N];
bool vis[N];

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i=2; i<=n; i++) {
        if(!vis[i]) prime[cnt++] = i;
        for(int j=0; j<cnt && i*prime[j]<=n; j++) {
            vis[i*prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    for(int i=0; i<cnt; i++) cout << prime[i] << " ";
    return 0;
}

三、对比与选择

方法	原理	复杂度
埃氏筛	删除倍数	O(n log log n)
线性筛	最小质因数	O(n)

• 小数据 (n ≤ 10^6)：推荐埃氏筛，简单好写。
• 大数据 (n ≥ 10^7)：推荐线性筛，速度更快。

总结

• 埃氏筛：发现素数 → 删除倍数。
• 线性筛：每个合数只筛一次。