质数线性筛, 欧拉筛法, O(n)时间复杂度

1. 首先看到这个题目的数据量，在最差情况下，也就是 ( n = 2 )，( m = 10^7 )。那么假如用暴力方法来做这道题，暴力算法需要遍历 ( m ) 的每一个数来判断其是否为质数，时间复杂度大致是：

显然是会超时的。

2. 那有什么比上述给出的时间复杂度更低的算法呢？可以在更小的时间量级下求解出 ( n ) 到 ( m ) 之间的质数吗？这时就轮到质数筛法（也叫欧拉筛法）上场了。

线性筛法

线性筛法（Linear Sieve）是一种用于高效求解素数的算法，时间复杂度为：

比传统的埃拉托斯特尼筛法：

更高效，尤其在处理较大的范围时。

工作原理

1. 初始化：创建一个布尔数组 is_prime，其中：

表示数字 ( i ) 是否是素数。初始时将所有数字设为素数（True）。

2. 筛选过程：从 2 开始，逐步检查每个数：

• 如果该数是素数（即：

为 True），则它会标记出所有它的倍数不是素数。

• 在标记倍数时，关键点是：对于每个素数 ( p )，我们从 ( p^2 ) 开始标记它的倍数，而不是从 ( 2p ) 开始，避免重复标记。

3. 不重复标记：线性筛法的一个关键特点是，当我们筛选一个素数 ( p ) 时，我们只将它的倍数：

标记为非素数，且 ( i >= p )，这样就避免了重复筛选，提高了效率。

具体步骤

1. 初始化一个布尔数组 is_prime，表示每个数是否是素数。
2. 对于每个数 ( i )（从 2 开始），如果：

为 True，说明 ( i ) 是素数。 3. 对于素数 ( i )，我们更新其倍数：

将它们标记为非素数，且 ( k >= i )。

• 时间复杂度：

比传统的埃拉托斯特尼筛法更高效。

• 空间复杂度：需要一个布尔数组存储素数信息，空间复杂度为：

相对较低。

示例代码（C++）

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> prime, is_p(m + 1, true);
    is_p[0] = false;
    is_p[1] = false;
    for (int i = 2; i <= m; i++) {
        if (is_p[i]) prime.push_back(i);
        for (auto p : prime) {
            if ((long long) p * i > m) break;
            is_p[p * i] = false;
            if (p % i == 0) break;
        }
    }
    for (auto x : prime) {
        if (x < n) continue;
        printf("%d\n", x);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define N 10000100
int pri[N], now = 0;
bool vis[N];
using i64 = long long;
inline void linerPrime()
{
    for(int i = 2; i <= N; i++)
    {
        if(!vis[i])
            pri[++now] = i; 
        for(int j = 1; j <= now && pri[j] * i <= N; j++)
        {
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0)
                break;
        }
    }
}
inline void solve()
{
    int min, max;
    cin >> min >> max;
    for(int i = 0; i < now; ++i)
        if(pri[i] >= min && pri[i] <= max)
            cout << pri[i] << std::endl;
    return;
}

int main()
{
    int t = 1;
    linerPrime();
    while(t--)
    {
        solve();
    }
    return 0;
}