P3383 【模板】线性筛素数

https://www.luogu.com.cn/problem/P3383

//线性筛法 /* P3383 【模板】线性筛素数 https://www.luogu.com.cn/problem/P3383数论 - 欧拉筛法（线性筛）的解释 https://blog.csdn.net/Losk_0/article/details/87884390素数筛法详解（欧拉筛&埃氏筛） https://blog.csdn.net/FeilingGong/article/details/83660779算法笔记（四）——欧拉筛法求素数 https://blog.csdn.net/weixin_42172676/article/details/81978475快速线性筛法的原理和值得借鉴的方法【解析算法】 https://blog.csdn.net/nuanxin_520/article/details/41207145快速线性筛法的特点就是不会重复筛除一个合数。它的原理是前提是：一个合数i=p1*p2*...*pn, pi都是素数（2<=i<=n），pi<=pj( i<=j )p1是最小的系数。这样每一个合数就有一个确定的表示方法，不会重复。（像12=2*2*3）No.1：我们现在规定一个合数由两个数得到。NO.2：那么合数有两种。1.素数*素数=合数 2.一个最小的素数*合数=合数筛除：如果遇到i为素数，那么一个大的素数 i 乘以不大于 i 的素数，这样筛除的数跟之前的是不会重复的如果遇到i为合数，我们只认为合数由一个最小的素数*合数得到，也不会重复（就像12=2*6而不是12=3*4）一般的线性筛法 https://www.cnblogs.com/KyleDeng/p/9244850.html*/ #include<bits/stdc++.h> using namespace std; int pr[8000010],c[100000010],n,m,s=0,x; int main() {memset(c,0,sizeof(c));scanf("%d%d",&n,&m);for(int i=2;i<=n;++i){if(c[i]==0){pr[++s]=i;}for(int j=1;j<=s && i*pr[j]<=n;++j){c[i*pr[j]]=1;if(i%pr[j]==0){break;}}}for(int i=1;i<=m;++i){scanf("%d",&x);printf("%d\n",pr[x]);}return 0; }

总结

以上是生活随笔为你收集整理的P3383 【模板】线性筛素数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。