欧拉筛是一种素数筛,避免了同一个数被多次筛除,可以在线性时间内找出指定范围内的素数。
筛选素数,一种较为朴素的想法是,对于已经得到的素数集合中的元素,枚举其倍数并筛除。但是,在这个过程中,会有同一个合数被筛多次的可能,例如,由于15=3*5,所以它既会被3所筛除,又会被5所筛除。由此可以自然地想到一种优化途径:通过制定一种规则,使得每个合数都只被筛除一次。
在这里,我们采用的方案是,让每一个合数都只被其最小的质因数筛除,也等价于让其只被最大的非自身因数筛除。
代码及详细注释如下:
#include <stdio.h>
#include <stdlib.h>
int state[100000005];
int prime[100000005];
int main()
{
int count=1,n,q,i,j,search;
state[1]=1;//1表示非质数
scanf("%d %d",&n,&q);
//对于每一个合数,都可以将它写成最大非自身因数乘以最小质因数的形式
for (i=2;i<=n;i++)//每一轮希望筛除以i为最大非自身因数的合数
{
if (state[i]==0)
{
prime[count++]=i;
//若i为合数,则一定已经被某个小于i的i1给筛除掉
//所以至今未被筛除的必为质数,加入质数表
}
//无论i是否为质数,都有资格作为最大非自身因数
for (j=1;j<count && prime[j]*i<=n;j++)
//枚举质数表,希望它成为与最大非自身因数对应的最小质因数
{
state[prime[j]*i]=1;//筛除操作
if (i%prime[j]==0) break;
//如果i以prime[j]为质因子,则继续向后枚举没有意义,理由如下:
//设k>j,则prime[k]>prime[j],i*prime[k]将以i的质因子prime[j]为最小的质因数
//也就是说,即使我现在不筛除掉i*prime[k],它也会被prime[j]乘以某个数所筛除
}
}
for (i=1;i<=q;i++)
{
scanf("%d",&search);
printf("%d\n",prime[search]);
}
}