质数筛

质数筛也是数论中非常重要的一个部分。

根号筛

这个是很多人第一个学的筛法，也是最简单的筛法。

做法很简单，就是枚举 $2$ 到 $n-1$ 里所有的数，如果当前数可以被 $n$ 整除，那么 $n$ 显然就是一个和数。直到跑完循环也没返回，就说明 $n$ 是一个指数。当然，$n<2$ 要特判，$n=2$ 也要特判。这样做每次判断一个数的时间复杂度是 $O(n)$，判断 $n$ 个数的时间复杂度是 $O(n^2)$。太慢了，要优化。

发现每当枚举的数 $\ge \sqrt n$ 时，这个数就已经被判断过了，所以只需要枚举 $2$ 到 $\sqrt n$ 的数就可以了，判断一个数的时间复杂度是 $O(\sqrt n)$，判断 $n$ 个数的时间复杂度是 $O(n\sqrt n)$。 注意点
1.注意循环到 $\sqrt n$ 时，不建议直接用

sqrt(n)

i*i<=n

i<=n/i

code

这里只给出判断的函数。

cpp
Copy
bool isprime(int x){
	if(x<2)return 0;
	if(x==2)return 1;
	for(int i=2;i<=x/i;i++){
		if(x%i==0)return 0;
	}
	return 1;
}

埃筛

埃筛，也叫埃氏筛，全称埃拉托斯特尼筛法。是一种高效的判断质数的筛法。

原理是这样的：因为每一个的倍数都是合数，所以可以从 $2$ 开始筛，如果当前的数标记为质数，就把它的倍数标成合数，如果是合数则直接跳过。埃筛的数也只需要枚举到 $\sqrt n$。 最后筛出来的标记数组就是每个数是质数还是合数的情况。 筛 $n$ 个数的时间复杂度是 $O(n\log\log n)$，我也不知道怎么证。

值得一提的是，因为埃筛只用一个

bool 

bitset

bool

bitset<N>prime

bitset<int>prime[N]

bitset<bool>prime[N]

code

如果使用

bool

bitset<N>prime;

bool prime[N];

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
int n,q;
bitset<N>prime;
int primes;
int cnt=0;
void init(int n){
	for(int i=2;i<=n/i;i++){
		if(prime[i])continue;
		for(int j=i+i;j<=n;j+=i){
			prime[j]=1;
		}
	}
	for(int i=2;i<=n;i++){
		if(!prime[i])cnt++;
	}
	cout<<cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	init(n);
	return 0;
}

线性筛

线性筛又名欧拉筛。顾名思义，它的时间复杂度是线性的，也就是 $O(n)$ 的。其实就是一种基于埃筛的优化。

当我们使用埃筛的时候，会发现，有一些数被重复筛了，比如 $6$ 就同时被 $2$ 和 $3$ 筛，这样多余的操作会使程序变慢，而线性筛是每个数只筛 $1$ 遍的。

操作如下： 用一个

primes

bool

st

primes

primes

primes[j]*i

primes[j]

break

primes[j]

primes

code

P3383 【模板】线性筛素数

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
int n,q;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i])primes[cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++){
			st[primes[j]*i]=true;
			if(i%primes[j]==0)break;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	get_primes(n);
	while(q--){
		int k;
		cin>>k;
		cout<<primes[k-1]<<'\n';
	}
	return 0;
}