欧拉筛

文章部分内容转载自算法学习笔记(17): 素数筛 - 知乎 (zhihu.com)、欧拉筛筛素数 - 洛谷专栏 (luogu.com.cn)，如有侵权，请联系作者删除。

不想再写一遍原理了qwq（如果忘记原理就去看看大佬们的详细证明吧，感觉注释也说得很清楚了@w@）。

所以我就直接贴上欧拉筛的模板了。

【模板】线性筛素数

题目背景

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

题目描述

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

输入格式

第一行包含两个正整数 \(n,q\)，分别表示查询的范围和查询的个数。

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

输出格式

输出 \(q\) 行，每行一个正整数表示答案。

样例 #1

样例输入 #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.

学委大佬的代码：

#include<iostream>
#include<cstring>
const int N = 1e8 + 10;
using namespace std;
bool isPrime[N];//isPrime[i]==1表示：i是质数
int Prime[N], cnt = 0;//Prime存质数
void getPrime(int n) {
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {//没被筛掉
			Prime[++cnt] = i;//i成为下一个素数
		}
		for (int j = 1; j <= cnt && i * Prime[j] <= n; j++) {
			//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
			//当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i * Prime[j]] = 0;
			if (i % Prime[j] == 0) break;
		}
	}
}
int main(){
	int n, q;
	cin >> n >> q;
	getPrime(n);
	while (q--) {
		int k;
		cin >> k;
		cout << Prime[k] << "\n";
	}
	return 0;
}

pecco大佬的代码：

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

两者的写法其实很相似了，如果忘记了原理，可以先看看学委大佬的，要写题的话，推荐用pecco大佬的板子。