LG3383线性筛.MD

日期 2022/03/15

[题目链接]https://www.luogu.com.cn/problem/P3383

题目

题目背景

本题已更新，从判断素数改为了查询第 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

解题思路

这个题目是一道线性筛模板题，线性筛的时间复杂度是O(n)是目前最快的素数筛法，线性筛的原理即我们知道一个合数=质数合数或者合数=质数质数，即每一个数都是由不用的质数相乘得来的(也有 可能是相同质数相乘）所以，线性筛即利用质数*遍历的某数来得到筛除合数， if (i % Prime[j] == 0) {break;}而这个式子又确定了我们筛除合数是利用最小质因数来筛的，排除了一个数 可能被多个数筛的情况

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 1, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e8 + 10;
using namespace std;

int cnt = 0;
bool isPrime[maxn];
int Prime[maxn];

void GetPrime(int n) {
  format(isPrime);
  isPrime[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      Prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && i * Prime[j] <= n; j++) {
      isPrime[i * Prime[j]] = 0;
      if (i % Prime[j] == 0) {
        break;
      }
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q, x;
  cin >> n >> q;
  GetPrime(n);
  for (int i = 0; i < q; i++) {
    cin >> x;
    cout << Prime[x] << endl;
  }
  return 0;
}