题解：P3383 【模板】线性筛素数

cxlqwq · 2025-05-22 21:29:56 · 题解

素数筛法

对于欧拉筛法，埃氏筛法仍然做了一些重复性的判断，比如 60 时取到素因子为 2、3、5 时均进行了标记，如果我们只用最小的质因数来进行筛选，则可以保证进行重复筛除，这样就可以把效率做到最好，这就是欧拉筛法。

欧拉筛法的算法步骤为：

1. 枚举 2\sim n 中的每一个数 i；
2. 如果 i 是素数，则保存在素数表中；
3. 利用 i 和素数表中的素数 prime_j 去筛除 i \times prime_j。为了确保 i \times prime_j 只被素数 prime_j 筛除，我们需要确保 prime_j 是 i \times prime_j 中最小的素因子。
4. 假设 i 中最小素因子是素数表中的 prime_k，显然当 j \leq k 时，prime_j \times i 都是可以被筛除的。
5. 当 j > k 时，由于 prime_k \mid i i \times prime_j = prime_k \times ( \frac {i}{prime_k} \times prime_j) prime_k < prime_j

void Euler_sieve(int n)
{
    memset(p, true, sizeof p);
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
        {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++)
        {
            p[i * prime[j]] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
}

每个数最多被筛选一次，时间复杂度 O(N)。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 100;
#define maxn 250005
#define mod 1e9 + 7
bool p[N];
int prime[N] = {0};
/*
void sieve(int n)//埃氏筛法
{
    memset(p, true, sizeof p);
    for (int i = 2; i * i <= n; i++)
    {
        if (p[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                p[j] = false;
            }
        }
    }
}
*/
void Euler_sieve(int n)
{
    memset(p, true, sizeof p);
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
        {
            prime[++prime[0]] = i;//把素数保存到素数表 prime 中
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++)
        {
            p[i * prime[j]] = false;//筛除 i*prime[j]
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main()
{
    int n, q, k;
    cin >> n >> q;
    Euler_sieve(n);//n 以内素数
    while (q--)
    {
        cin >> k;
        cout << prime[k] << "\n";//第 k 小素数
    }
    return 0;
}