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

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

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

• 题目背景
• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 说明/提示
• C++代码

---

题目背景

本题已更新，从判断素数改为了查询第 (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 le q le 10^6)，保证查询的素数不大于 (n)。

Data by NaCly_Fish.

C++代码

#include <cstdio>
using namespace std;

int a[100000005], c[100000005];

int main() {
    int n, q, k=1;
    scanf("%d%d", &n, &q);
    int b[q];
    for (int i=0; i<q; ++i)
        scanf("%d", &b[i]);
    c[1] = 1;
    for (int i=2; i<=n; ++i) {
        if (c[i] == 0)
            a[k++] = i;
        for (int j=1; j<k && i*a[j]<=n; ++j) {
            c[i*a[j]] = 1;
            if (i % a[j] == 0)
                break;
        }
    }
    for (int i=0; i<q; ++i)
        printf("%d
", a[b[i]]);
    return 0;
}