【模板】【线性筛】

众所周知，即使是经过优化的埃氏筛，其复杂度依然为O(N log log N)

但我们需要一个O(N)的算法————线性筛

我们发现之所以埃氏筛会重复标记合数，是因为其没有确定该合数的唯一产生方式

线性筛的对策是————只用该合数的最小质因子标记该合数

于是，我们用一个v数组记录2~N中每个数的最小质因子

算法流程

1. 枚举i从2~N;
2. 若v[i]==0，即没有被标记过，说明i为质数，将i加入质数集合，并标记v[i]=i;
3. 扫描不大于v[i]的每个质数p，令v[i*p]=p。

正确性

为什么所有合数在这个过程中都会被标记？因为任意一个合数i都一定能用它的最小质因子p0与一个小于i的整数i/p0的积表示
额……然后就证完了？（毕竟确实很显然）

Code

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘) ch=getchar();
	if(ch==‘-‘){ch=getchar();w=-1;	}
	while(ch>=‘0‘&&ch<=‘9‘) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();	}
	return x*w;
}
const int M=1e8+10;
int n,q,k,cnt;
int v[M],prime[M/8+100];
int main()
{
	n=read();
	q=read();
	for(int i=2;i<=n;++i)
	{
		if(v[i]==0){
			prime[++cnt]=i;
			v[i]=i;
		}
		for(int j=1;j<=cnt;++j)
		{
			if(prime[j]>v[i]||prime[j]*i>n) break;
			v[prime[j]*i]=prime[j];
		}
	}
	for(int i=1;i<=q;++i){
		k=read();
		printf("%d\n",prime[k]);
	}
	return 0;
} 

【模板】【线性筛】