欧拉筛，是一种可以O(n)筛出1~n范围内的素数的筛法，比naive筛的O(nlogn)，埃式筛的O(nloglogn)都要快一些，还可以根据题目搞出一些最大约数啊之类的东西
代码:
void Euler_pick(int n) { for(int i=2;i<=n;i++) { if(!vis[i]) p[++cnt]=i; for(int j=1;p[j]*i<=n;j++) { vis[p[j]*i]=1; if(i%p[j]==0) break; } } }
p是用于存储素数的
相信你可能对于"i%p[j]==0,break"这句话有疑问
首先你要知道，欧拉筛的核心是保证每个合数，只会被最小的质因子筛掉。
我们可以这样来想，在筛掉p1*i后，我们会判断i的约数里面是否有p[1]。
假如有p[1]的话，如果此时我们执行j++而不是break，我们会发现，p[2]就不是i*p[2]的最小质因子了，因为i的约数里有p[1]，而p[1]<p[2]。
这样一想就好了
转载于:https://www.cnblogs.com/Patrickpwq/articles/9615636.html
