洛谷题单指南-数学基础问题-P3383 【模板】线性筛素数

原题链接：https://www.luogu.com.cn/problem/P3383

题意解读：素数筛模版题。

解题思路：

素数筛介绍

所谓素数（质数），是指除了1和它本身以外不再有其他因数的自然数，一般用试除法判断素数（时间复杂度：O(sqrt(n))）：

bool isprime(int x)
{
    if(x <= 1) return false;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0) return false;
    }
    return true;
}

注意：如果i比较大，i * i <= x有溢出风险，写成i <= x / i比较安全。

所谓素数筛，就是在一定范围内，筛出所有的素数。

例如要筛出1~n中所有的素数，如果枚举每一个数去判断是否是素数，时间复杂度为O(n*sqrt(n))，当n=10⁶都无法应对，因此出现了素数筛算法。

素数筛算法的核心思想是通过遍历2~n，将每个数的若干倍数都标记为合数，这样剩下的就都是素数，根据优化程度不同有三种算法：

a、朴素筛法：时间复杂度O(n*logn)

对于2~n中每一个数，如果没有标记成合数，则保存为素数，再将该数的2倍、3倍、4倍...标记为合数，代码如下：

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//朴素筛，筛出1 ~ N之间的素数，复杂度O(nlogn)
void getprimes1()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) primes[cnt++] = i; //如果i未被标记合数，则保存i为素数
        for(int j = i + i; j <= N; j += i) //把i的倍数都标记为合数
            flag[j] = true;
    }
}

int main()
{
    getprimes1(); 
    return 0;
}

b、埃氏筛法：时间复杂度O(n*loglogn)

由于在标记合数时，无论当前i是素数还是合数，都将其倍数进行了标记，这样必然导致大量重复标记。

例如：i=2时，i*4=8；而i=4时，又有i*2=8；8被重复标记

埃氏筛就是在朴素筛的基础上做出优化，只将素数的倍数进行标记，合数的倍数不标记，这样可以一定程度减少重复标记，代码如下：

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//埃氏筛，筛出1 ~ N之间的素数，复杂度O(nloglogn)
void getprimes2()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) //如果没有被标记为合数
        {
            primes[cnt++] = i; //保存素数
            for(int j = i + i; j <= N; j += i) //只对素数的倍数进行标记
                flag[j] = true;
        }
    }
}

int main()
{
    getprimes2(); 
    return 0;
}

c、线性筛法：时间复杂度O(n)

尽管埃氏筛只针对素数的倍数进行标记，但是还是会有一定程度的重复标记。

例如：i=2时，2*3=6；i=3时，i*2=6；6被重复标记。

线性筛在埃氏筛的基础上又进一步优化，使得每个合数只被它最小的素因子标记，这样每个合数都只被标记一次，如何做到呢？

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//线性筛，筛出1 ~ N之间的素数，复杂度O(n)
void getprimes3()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) primes[cnt++] = i; //如果i未标记为合数，则保存为素数
        for(int j = 1; j <= cnt; j++) //从小到大遍历每一个已保存的素数，要将i * primes[j]标记为合数
        {
            if(i * primes[j] > N) break; //超出最大值
            flag[i * primes[j]] = true; //将i * primes[j]标记为合数，primes[j]必然是i * primes[j]的最小素因子
            if(i % primes[j] == 0) break; //当i中包含一个primes[j]因子，就不能用此i去标记下一个数i * primes[j+1]，因为i * primes[j+1]包含因子primes[j]，而primes[j+1]不是最小素因子
        }
    }
}

int main()
{
    getprimes3(); 
    return 0;
}

本题数据量在10^8，直接用线性筛求解。

100分代码：

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

const int N = 1e8 + 5;

int primes[N], cnt;
bool flag[N];
int n, q, k;

int main()
{
    scanf("%d%d", &n, &q);

    for(int i = 2; i <= n; i++)
    {
        if(!flag[i])  primes[++cnt] = i;
        for(int j = 1; j <= cnt; j++)
        {
            if(i * primes[j] > n) break;
            flag[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }

    while(q--)
    {
        scanf("%d", &k);
        printf("%d\n", primes[k]);
    }
    
    return 0;
}