数论模板1 :欧拉筛的主题传送门
这里直接介绍欧拉筛法。 该算法的时间复杂度为o(n )，每个数由最大的自生成因子筛选，保证每个数只筛选一次。 具体代码如下。
# include bits/stdc.husingnamespacestd； int n、q、cnt=0； bool isprime[100000001]； int prime[100000001]； int main () Scanf ) ' %d%d '，n，q )； memset(isprime，true，sizeof ) isprime )； //点1for(intI=2； i=n； I () if ) isprime[I] ) {prime[ cnt]=i； }for(intj=1； j=cntprime[j]*i=n； j({isprime[prime]*I )=false； if(I%prime[j]==0) break； //点2}}int c[q]； for(intI=0； 智商； I )扫描(“% d”，c[i]； for(intI=0； 智商； I ) printf('%d(n )，prime[c[i]] )； 返回0； }如图所示，预先加一个布尔数组isprime，检查某个数是否为素数，再加一个prime记录所有素数。 cnt是素数的个数，n、q是主题要求的数字，在此不做说明。
首先，假设所有的数都是素数。 假设0和1为false。 现在，从2到n开始循环。 循环的值为倍数I。 如果与isprime对应的值为true，则将该数添加到prime数组中。
接下来，我们将考虑该算法的方法。
首先，让我证明一个引理。 每个数n可以写几个质因数的乘积。
n=2时，明显成立。
假设这个定理对于小于任意n的正整数成立。
如果n为整数，则有n=n1n2 1n1n 1n2n，根据归纳假设，n1=a1a2*…aj n2=b1b2*…bk通过先前的归纳假设证明n1、n2都是素数积，由于集合的良序性，http://
现在，分析迄今为止采集的所有素数，筛出他们所有I的倍数。
重要优化： if(I%prime[j]==0) break；
对数iprime[j]很好理解。 当i%prime[j]为零时，表示I不是该数量的最大因子。 那接下来的iprime[j 1]呢？
当i%prime[j]=0时，存在整数k=i/prime[j]，iprime[j 1]=k*prime[j]prime[j 1]
很明显，kprime[j 1]是一个大于I的因子，因为它随后被过筛一次，防止直接跳出循环。