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. 核心思想