前往：我自己搭建的博客
题目
洛谷P3383线性筛素数
题解
筛法的本质是标记合数，即标记每个数的所有倍数。但在标记时，一个合数会被它的所有质因子重复标记多次，导致时间的浪费。因此，考虑让每个合数只被自己的最小质因数标记。
算法流程：用v[i]表示i的最小质因数，用不大于v[i]的所有质数p标记合数i*p，并更新v[i*p]=p。
1~n之间的素数个数约为 。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e8+5;
const int maxp=5e6;
int n,m,q;
int v[maxn],prime[maxp];
inline void get_prime()
{
for(int i=2;i<=n;i++) //注意从2开始循环
{
if(!v[i]) {v[i]=i; prime[++m]=i;}
for(int j=1;j<=m;j++)
{
if(prime[j]>v[i]||prime[j]*i>n) break;
v[i*prime[j]]=prime[j];
}
}
}
int main()
{
scanf("%d%d",&n,&q);
get_prime();
for(int i=1;i<=q;i++)
{
int k; scanf("%d",&k);
printf("%d\n",prime[k]);
}
return 0;
}
