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

素数筛法

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

欧拉筛法的算法步骤为：

枚举 $2\sim n$ 中的每一个数 $i$ ；
如果 $i$ 是素数，则保存在素数表中；
利用 $i$ 和素数表中的素数 $prime_j$ 去筛除 $i \times prime_j$ 。为了确保 $i \times prime_j$ 只被素数 $prime_j$ 筛除，我们需要确保 $prime_j$ 是 $i \times prime_j$ 中最小的素因子。
假设 $i$ 中最小素因子是素数表中的 $prime_k$ ，显然当 $j \leq k$ 时， $prime_j \times i$ 都是可以被筛除的。
当 $j > k$ 时，由于 $prime_k \mid i$ $i \times prime_j = prime_k \times ( \frac {i}{prime_k} \times prime_j)$ $prime_k < prime_j$ $prime_j \times i$ 不应该在此筛除，而应在 $i$ 循环执行到 $\frac {i}{prime_k} \times prime_j$ 时，与素数表的 $prime_j$ 相乘才筛除，因此，需要在 $i \mid prime_j$ 时结束 $j$ 循环。

CPP

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

CPP

#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;
}

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

文章操作

素数筛法

AC Code

相关推荐

评论

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