当前没有测试数据。

线性筛与埃氏筛详解

前言

线性筛（欧拉筛）是埃氏筛的进阶版。埃氏筛的时间复杂度为 O(n log log n)，而线性筛的时间复杂度为 O(n)。但对于大多数OJ题目来说，埃氏筛通常已经足够满足需求。

注意：时间复杂度表示应使用标准格式，即 O(n log log n) 而非 O（n*loglogn）。

一、埃氏筛（Sieve of Eratosthenes）

埃氏筛，全名埃拉托斯特尼筛法，是一种古老且简单的素数筛选算法，公元前250年由希腊数学家埃拉托斯特尼提出。

算法思想

一个素数的整数倍一定是合数。

代码实现

#include <bits/stdc++.h>
using namespace std;

int p[1000010], a[1000010]; // p数组存储素数，a数组标记是否为素数

int main() {
    int n, k = 0;
    cin >> n;
    
    // 初始化：假设所有数都是素数（标记为1）
    for (int i = 1; i <= n; i++) a[i] = 1;
    a[0] = 0, a[1] = 0; // 0和1不是素数
    
    for (int i = 2; i <= n; i++) {
        if (a[i] == 1) {
            p[++k] = i; // 记录素数
        } else {
            continue; // 不是素数则跳过
        }
        
        // 标记素数i的所有倍数为合数
        for (int j = 2; j * i <= n; j++) { // 从2倍开始标记
            a[j * i] = 0;
        }
    }
    
    // 输出素数个数
    cout << k << endl;
    // 输出所有素数
    for (int i = 1; i <= k; i++) {
        cout << p[i] << endl;
    }
    
    return 0;
}

二、线性筛（欧拉筛）的改进

埃氏筛存在重复标记的问题。例如数字30会被标记3次：

• 2 × 15
• 3 × 10
• 5 × 6

线性筛的思想是在埃氏筛的基础上，确保每个合数只被其最小质因子筛掉一次，从而将时间复杂度降为O(n)。

三、算术基本定理与最小质因子

算术基本定理

任何一个大于1的自然数N，如果N不是素数，那么N可以唯一分解成有限个质数的乘积。

最小质因子

一个合数分解出的有限个质数乘积中，最小的那个质数称为最小质因子。

线性筛的核心思想是：每个合数只通过它的最小质因子被标记一次。

四、线性筛的代码实现

#include <bits/stdc++.h>
using namespace std;

int p[1000010], a[1000010]; // p存储素数，a标记是否为素数（1为素数，0为合数）

int main() {
    int n, k = 0;
    cin >> n;
    
    // 初始化：假设所有数都是素数
    for (int i = 1; i <= n; i++) a[i] = 1;
    a[0] = 0, a[1] = 0; // 0和1不是素数
    
    for (int i = 2; i <= n; i++) {
        if (a[i] == 1) {
            p[++k] = i; // i是素数，加入素数数组
        }
        
        // 用当前数i乘以已知素数来筛合数
        for (int j = 1; j <= k && i * p[j] <= n; j++) {
            a[i * p[j]] = 0; // 标记i*p[j]为合数
            
            // 关键步骤：保证每个合数只被最小质因子筛掉
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    
    // 输出结果
    cout << k << endl;
    for (int i = 1; i <= k; i++) {
        cout << p[i] << endl;
    }
    
    return 0;
}

关键代码解析：if (i % p[j] == 0) break;

为什么当i是p[j]的倍数时要break？

我们需要确保每个合数只被其最小质因子筛掉。

• 情况分析：

  1. 当 i % p[j] != 0 时：

     • p[j] 不是 i 的因子
     • 所以 p[j] 是 i * p[j] 的最小质因子（因为p数组是递增的）

  2. 当 i % p[j] == 0 时：

     • 设 i = k * p[j]（k为正整数）
     • 那么 i * p[j+1] = k * p[j] * p[j+1]
     • 由于 p[j] < p[j+1]，所以 p[j] 才是 i * p[j+1] 的最小质因子
     • 如果继续用 p[j+1] 去筛，就会导致 i * p[j+1] 被非最小质因子筛掉，造成重复
     • 因此需要break，让 i * p[j+1] 在未来被 p[j] 筛掉

举例说明：

• 当 i = 4，p[j] = 2 时：
  • 4 % 2 == 0，需要break
  • 如果不break，下一步会计算 4 * 3 = 12
  • 但12的最小质因子是2，应该在 i = 6 时用 p[j] = 2 来筛（6 * 2 = 12）
  • 这样12只会被筛一次（被最小质因子2筛）

算法对比

总结

1. 埃氏筛简单易懂，适合初学者理解素数筛选的基本思想
2. 线性筛通过避免重复标记，达到了理论上的最优时间复杂度
3. 在实际编程中，根据数据规模选择合适的算法：
   • n ≤ 10⁶：埃氏筛通常足够
   • n > 10⁷：建议使用线性筛