分配存储

• bool isprime[N]： isprime[k]=true表示 $k$ 是质数
• ll prime[N]： prime[i]是第 $i$ 个质数，索引从 $1$ 开始
• ll cnt表示当前质数数量

核心思想

通过

筛去所有 $n$ 以内的合数，留下的就是质数。 枚举 $k$ ，再对每个 $k$ 枚举不大于其的质数 $p_i$，若中途发现某一 $p_i\nmid k$，对于所有之后要枚举的 $p_j$，$p_i\mid p_jk$，必有一质因数小于枚举中的质数 $p_j$，所以肯定会被重复枚举，处理完 $p_i$ 后直接退出该层的循环即可。 即：

//....
if(i % p[j] == 0) break;

算法步骤

• 假设所有数均是质数，初始化 isprime全为true
• $1$ 不是质数，设置isprime[1] = false
• 枚举 $k\quad(2\leq k\leq n)$
  • 若 $k$ 未被筛过，则将其添加至质数列表
  • 枚举已知的质数 $p_i\quad(1\leq i\leq \mathtt{cnt})\quad(p_ik\leq n)$
    • 筛去 $p_ik$
    • 若 $p_i\nmid k$ 则跳出循环，处理下一个 $k$

最后prime[]数组即是从小到大的质数列表。

参考代码

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

bool isp[100000005];
ll p[10000005], cnt = 0;

void getp(ll n) {
  memset(isp, true, sizeof(isp));
  isp[1] = false;
  REP(i, 2, n) {
    if (isp[i]) p[++cnt] = i;
    REP(j, 1, cnt) {
      if (i * p[j] > n) break;
      isp[i * p[j]] = false;
      if (i % p[j] == 0) break;
    }
  }
}

signed main() {
  ll n, q, k;
  scanf("%lld%lld", &n, &q);
  getp(n);
  while (q--) {
    scanf("%lld", &k);
    printf("%lld\n", p[k]);
  }
}

// https://www.luogu.com.cn/record/60897651