深入解析素数筛法：从埃氏筛到欧拉筛的算法思想与实现

        素数筛法是一种用于高效生成素数的算法。常见的素数筛法包括埃拉托斯特尼筛法（埃氏筛）和欧拉筛（线性筛）。下面我们将详细讲解这两种筛法的思想：

一、 埃拉托斯特尼筛法（埃氏筛）

思想：

        埃氏筛的基本思想是从2开始，将每个素数的倍数标记为合数，直到筛完所有小于等于给定范围的数。具体步骤如下：

1. 初始化一个布尔数组 isPrime[]，大小为 n+1，并将所有元素初始化为 true。

2. 从2开始遍历到 sqrt(n)，如果当前数 i 是素数（即 isPrime[i] 为 true），则将其所有倍数标记为合数（即 isPrime[j] 设为 false）。

3. 最后，所有 isPrime[i] 为 true 的 i 即为素数。

时间复杂度：

埃氏筛的时间复杂度为 O(n log log n)。

未优化代码实现：

const int N = 1e7; // 定义空间大小，1e7 约 10MB
int prime[N+1]; // 存放素数，记录 visit[i] = false 的项
bool visit[N+1]; // visit[i] = true 表示 i 被筛掉，不是素数int E_sieve(int n) { // 埃氏筛法，计算 [2,n] 内的素数int k = 0; // 统计素数的个数for(int i = 0; i <= n; i++) visit[i] = false; // 初始化for(int i = 2; i <= n; i++) { // 从第一个素数 2 开始if(!visit[i]) { // 如果 i 是素数prime[++k] = i; // 将 i 存入 prime 数组for(int j = 2*i; j <= n; j += i) // 筛掉 i 的倍数visit[j] = true; // 标记为非素数}}return k; // 返回素数的个数
}

上述代码有两处可以优化：

（1）用来做筛选的数2、3、5等，最多到sqrt（n）就可以了。例如，求n=100以内的素数，用2、3、5、7筛选就足够了。其原理和试除法一样；非素数k，必定可以被一个小于或等于sqrt（k）的素数整除，被筛掉。这个优化很大，缩短了时间复杂度。

（2）for(int j = 2*i; j <= n; j += i)中的j=2*i优化为j=i*i。例如i=5，2*5,3*5,4*5已经在前面i=2,3,4的时候筛过了。这个优化较小，形如一个正方形的数组矩阵被砍成一个三角形。

优化代码实现： 

int E_sieve(int n) {for(int i = 0; i <= n; i++) visit[i] = false; // 初始化for(int i = 2; i <= sqrt(n); i++) // 只需筛到 sqrt(n)if(!visit[i]) // 如果 i 是素数for(int j = i * i; j <= n; j += i) // 从 i^2 开始筛visit[j] = true; // 标记为非素数int k = 0;for(int i = 2; i <= n; i++)if(!visit[i]) prime[++k] = i; // 存素数return k; // 返回素数的个数
}

埃氏筛的计算复杂度:

        2的倍数被筛掉,计算n/2次；3的倍数被掉，计算n/3次；5的倍数被筛掉，计算n/5次；……；总计算量等于n/2+n/3+n/5+n/7+n/11+…，约为O(n log log n)。其计算量很接近线性的(n)，已经相当好了。

空间复杂度:

        代码用到了bool visit[N+1]数组，当N=10^7时约10MB。由于埃氏筛只能用于处理约n=10^7的问题,10MB空间是够用的。
        埃氏筛可以计算出[2,n]内的素数，不过更常见的应用场景是计算[L,R]区间内的素数，L、R极大，但R一L较小，此时也可以用埃氏筛。

最终C++代码实现：

#include <iostream>  // 引入输入输出流库，用于标准输入输出（如cout）
#include <vector>    // 引入向量库，用于动态数组的实现
#include <cmath>     // 引入数学库，用于数学函数（如sqrt）// 定义埃拉托斯特尼筛法函数，参数n表示筛选素数的范围
void sieveOfEratosthenes(int n) {// 创建一个大小为n+1的布尔向量isPrime，初始值为true，表示所有数默认是素数std::vector<bool> isPrime(n + 1, true);// 0和1不是素数，手动设置为falseisPrime[0] = isPrime[1] = false;// 从2开始遍历到sqrt(n)，因为大于sqrt(n)的数的倍数已经被更小的素数标记过了for (int i = 2; i <= std::sqrt(n); ++i) {// 如果当前数i是素数（isPrime[i]为true）if (isPrime[i]) {// 从i的平方开始，将i的所有倍数标记为合数（false）// 因为小于i的倍数已经被更小的素数标记过了for (int j = i * i; j <= n; j += i) {isPrime[j] = false;}}}// 输出所有素数for (int i = 2; i <= n; ++i) {// 如果isPrime[i]为true，说明i是素数，输出iif (isPrime[i]) {std::cout << i << " ";}}// 输出换行符，使结果更美观std::cout << std::endl;
}// 主函数
int main() {int n = 50;  // 定义筛选范围的上限为50sieveOfEratosthenes(n);  // 调用埃拉托斯特尼筛法函数return 0;  // 程序正常结束
}

---

二、 欧拉筛（线性筛）

思想：

        欧拉筛是一种改进的筛法，能够在 O(n) 的时间复杂度内筛出所有素数。其核心思想是让每个合数只被其最小的质因数筛掉，从而避免重复标记。具体步骤如下：

1. 初始化一个布尔数组 isPrime[]，大小为 n+1，并将所有元素初始化为 true。

2. 初始化一个数组 primes[] 用于存储素数。

3. 从2开始遍历到 n，如果当前数 i 是素数，则将其加入 primes[]。

4. 对于每个素数 primes[j]，如果 i * primes[j] 超过 n 则停止；否则将 isPrime[i * primes[j]] 设为 false。如果 i 能被 primes[j] 整除，则停止内层循环。

时间复杂度：

欧拉筛的时间复杂度为 O(n)。

C++实现：

#include <iostream>
#include <vector>void eulerSieve(int n) {std::vector<bool> isPrime(n + 1, true);std::vector<int> primes;for (int i = 2; i <= n; ++i) {if (isPrime[i]) {primes.push_back(i);}for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {isPrime[i * primes[j]] = false;if (i % primes[j] == 0) {break;}}}// 输出所有素数for (int prime : primes) {std::cout << prime << " ";}std::cout << std::endl;
}int main() {int n = 50;eulerSieve(n);return 0;
}

总结：

• 埃氏筛：简单易懂，时间复杂度为 O(n log log n)，适合用于较小的范围。

• 欧拉筛：时间复杂度为 O(n)，适合用于较大的范围，且避免了重复标记。

三、 例题讲解

P1835 素数密度 - 洛谷

算法代码： 

#include<bits/stdc++.h> // 包含标准库中的所有头文件
using namespace std; // 使用标准命名空间
const int N=1e6+1; // 定义常量 N，表示数组的最大大小
int prime[50000]; // 用于存储素数的数组
bool vis[N+1]; // 用于标记是否为素数的布尔数组int E_sieve(int n) // 埃氏筛法函数，用于找出小于等于 n 的所有素数
{for(int i=0;i<=n;i++) // 初始化 vis 数组{vis[i]=false; // 将所有元素初始化为 false，表示初始时都认为是素数}for(int i=2;i<=sqrt(n);i++) // 从 2 开始筛除非素数{if(!vis[i]) // 如果 i 是素数{for(int j=i*i;j<=n;j+=i) // 筛除 i 的所有倍数{vis[j]=true; // 标记为非素数}}}int k=0; // 用于统计素数的个数for(int i=2;i<=n;i++) // 遍历所有数{if(!vis[i]) // 如果 i 是素数{prime[++k]=i; // 将素数存入 prime 数组}}return k; // 返回素数的个数
}int main() // 主函数
{int cnt=E_sieve(50000); // 调用埃氏筛法函数，找出小于等于 50000 的所有素数，并返回素数的个数int L,R; // 定义区间 [L, R]cin>>L>>R; // 输入区间 [L, R]if(L==1) // 如果 L 为 1，将其调整为 2，因为 1 不是素数{L=2;}memset(vis,0,sizeof(vis)); // 初始化 vis 数组为 0for(int i=1;i<=cnt;i++) // 遍历所有素数{int p=prime[i]; // 获取当前素数long long start; // 定义筛除的起始位置if((L+R-1)/p*p>2*p) // 计算起始位置{start=(L+p-1)/p*p;}else{start=2*p;}for(long long j=start;j<=R;j+=p) // 筛除当前素数的倍数{vis[j-L+1]=true; // 标记为非素数}}int ans=0; // 用于统计区间 [L, R] 内的素数个数for(int i=1;i<=R-L+1;++i) // 遍历区间 [L, R]{if(!vis[i]) // 如果当前数是素数{ans++; // 素数个数加 1}}cout<<ans; // 输出区间 [L, R] 内的素数个数
}

代码思路

        这段代码的主要功能是使用埃氏筛法找出给定区间 [L, R] 内的所有素数，并输出该区间内素数的个数。以下是代码的思路和实现步骤：

---

1. 包含头文件和定义常量

• 包含标准库头文件 <bits/stdc++.h>，以便使用所有标准库函数。

• 定义常量 N 表示数组的最大大小，prime 数组用于存储素数，vis 数组用于标记是否为素数。

---

2. 埃氏筛法函数 E_sieve

• 功能：找出小于等于 n 的所有素数。

• 实现步骤：

  1. 初始化 vis 数组，将所有元素标记为 false，表示初始时所有数都被认为是素数。

  2. 从 2 开始遍历到 sqrt(n)，筛除非素数：

     • 如果当前数 i 是素数（vis[i] == false），则筛除 i 的所有倍数（从 i*i 开始，步长为 i）。

     • 将筛除的数标记为 true，表示它们是非素数。

  3. 遍历所有数，将未被筛除的数（即素数）存入 prime 数组。

  4. 返回素数的个数。

---

3. 主函数 main

• 功能：计算区间 [L, R] 内的素数个数。

• 实现步骤：

  1. 调用 E_sieve 函数，找出小于等于 50000 的所有素数，并返回素数的个数 cnt。

  2. 输入区间 [L, R]。

  3. 如果 L == 1，将其调整为 2，因为 1 不是素数。

  4. 初始化 vis 数组为 0，用于标记区间 [L, R] 内的数是否为素数。

  5. 遍历所有素数 prime[i]：

     • 计算当前素数 p 在区间 [L, R] 内的起始筛除位置 start。

     • 从 start 开始，筛除 p 的所有倍数，并将这些数标记为非素数。

  6. 统计区间 [L, R] 内未被标记的数（即素数）的个数 ans。

  7. 输出 ans。

---

4. 关键点

• 埃氏筛法：用于高效找出小于等于 n 的所有素数。

• 区间筛法：利用埃氏筛法找出的素数，筛除区间 [L, R] 内的非素数。

• 起始位置计算：

  • 对于每个素数 p，筛除的起始位置为 max(p * 2, (L + p - 1) / p * p)。

  • 这样可以避免重复筛除已经在之前步骤中处理过的数。

---

5. 代码优化

• 空间优化：使用 vis 数组标记区间 [L, R] 内的数是否为素数，而不是整个范围 [1, N]。

• 时间优化：只筛除区间 [L, R] 内的数，避免不必要的计算。

---

代码流程图

1. 初始化：

   • 定义常量、数组和变量。

   • 调用 E_sieve 函数，找出小于等于 50000 的所有素数。

2. 输入区间 [L, R]：

   • 如果 L == 1，调整为 L = 2。

3. 筛除区间 [L, R] 内的非素数：

   • 遍历所有素数 prime[i]。

   • 计算起始位置 start。

   • 筛除 p 的所有倍数，并标记为非素数。

4. 统计素数个数：

   • 遍历区间 [L, R]，统计未被标记的数的个数。

5. 输出结果：

   • 输出区间 [L, R] 内的素数个数。

定位的数学思路：（难想咯）