当前没有测试数据。

线性筛法（欧拉筛法）介绍

一、算法背景

线性筛法（Linear Sieve，又称欧拉筛法）是埃拉托色尼筛法的改进版本,20世纪后期到21世纪初，程序竞赛和算法研究领域发展出一种改进版的筛法—— 每个合数只被它的最小质因子筛一次，避免重复标记。 为致敬欧拉对数论的贡献，人们习惯称之为“欧拉筛法”。

相较于埃拉托色尼筛法的时间复杂度为 $O(n\log\log n)$，欧拉筛能够做到每个合数只被其最小质因子标记一次，从而实现真正的线性时间复杂度，适用于大规模素数筛选任务，尤其在算法竞赛中尤为常见。

二、算法原理

给定一个整数 $n$，我们希望找出 $[2,n]$ 区间内的所有质数。

欧拉筛的基本思想如下：

1. 初始化一个布尔数组 is_prime[2..n] 全部置为 true；

2. 维护一个质数列表 primes；

3. 从 $i = 2$ 开始遍历到 $n$：

   • 若 is_prime[i] == true，说明 $i$ 是质数，加入 primes 列表；
   • 枚举所有已经得到的质数 $p$，对 $i$ 乘上 $p$ 进行标记，即 $i \times p$ 为合数；
   • 若 $i % p == 0$，说明 $p$ 是 $i$ 的最小质因子，则不再继续（避免重复标记）。

该筛法保证每个合数只被其最小质因子筛去一次，从而使时间复杂度降为 $O(n)$。

三、算法实现（C++ 示例）

const int N = 1e7;
bool is_prime[N + 1];
int primes[N], cnt = 0;

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = true;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt; j++) {
            if(i * prime[j] > n) break;
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}