P3383 【模板】线性筛素数---洛谷

雨点打透心脏的1/2处 2023-07-18 06:54 8阅读 0赞

## 题目描述 ##

题目背景  
本题已更新，从判断素数改为了查询第 k 小的素数  
提示：如果你使用 cin 来读入，建议使用 std::ios::sync\_with\_stdio(0) 来加速。

题目描述  
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。

输入格式  
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。

接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。

输出格式  
输出 q 行，每行一个正整数表示答案。

输入输出样例  
输入 \#1 复制  
100 5  
1  
2  
3  
4  
5  
输出 \#1 复制  
2  
3  
5  
7  
11  
说明/提示  
【数据范围】  
对于100% 的数据，n = 10^8,1≤q≤10 ^6  
，保证查询的素数不大于 n。

Data by NaCly\_Fish.

## 简单说下这题 ##

这道题目需要用到欧拉筛法求素数，那么欧拉筛法的原理是什么呢？它用到了一个结论：**最小质因子\*最大因子=合数**，如果是埃氏筛法筛法的话，众所周知，它的时间复杂度不是线性的，因为它在筛素数的时候有重复判断的过程，例如3与2的公倍数有6，12，18，其实6，12，18这些公倍数在2的时候就已经判断过了，所以在3的时候就没必要再判断，欧拉筛法就是避免了这些重复的判断。如果是欧拉筛法的话，我们只利用它的最小质因子来筛，过程就是线性的，因为每个数字对应只判断一次（相对应的意思是每个数的最小质因子只有一个，所以只能判断一次）。

代码如下：

#include<stdio.h>
    bool is_prime[100000008];
    int num[1000006];
    int cur=1;
    int n,p;
    void get_prime()
    {
        
        for(int i=2; i<=n; i++)
        {
        
            if(!is_prime[i])
                num[cur++]=i;
            for(int j=1; j<cur&&i*num[j]<=n; j++)
            {
        
                is_prime[i*num[j]]=1;
                if(!(i%num[j]))
                    break;
            }
        }
    }
    int main()
    {
        
        scanf("%d%d",&n,&p);
        get_prime();
        for(int i=0; i<p; i++)
        {
        
            int x;
            scanf("%d",&x);
            printf("%d\n",num[x]);
        }
        return 0;
    }