杭州做网站软件,一站式服务包括哪些内容,效果图制作收费标准,深入浅出wordpress【题目来源】 https://www.luogu.com.cn/problem/P3383 【题目描述】 给定一个范围 n#xff0c;有 q 个询问#xff0c;每次输出第 k 小的素数。 【输入格式】 第一行包含两个正整数 n#xff0c;q#xff0c;分别表示查询的范围和查询的个数。 接下来 q 行每行一个正整…【题目来源】https://www.luogu.com.cn/problem/P3383【题目描述】给定一个范围 n有 q 个询问每次输出第 k 小的素数。【输入格式】第一行包含两个正整数 nq分别表示查询的范围和查询的个数。接下来 q 行每行一个正整数 k表示查询第 k 小的素数。【输出格式】输出 q 行每行一个正整数表示答案。【输入样例】100 512345【输出样例】235711【数据范围】对于 100% 的数据n10^81≤q≤10^6保证查询的素数不大于 n。【算法分析】● 素数判断的经典代码如下所示。但是当 n 较大时如 1e8会非常耗时‌最终导致 TLE。bool isPrime(int n) { if(n2) return false; for(int i2; isqrt(n); i) { if(n%i0) return false; } return true; }● 解决方法是先用高效的素数筛选算法埃氏筛/欧拉筛预处理出 1e8 以内的所有素数并存储再通过数组直接查询第 k 小的素数数组下标对应排名。其中静态埃氏筛详见 →https://blog.csdn.net/hnjzsyjyj/article/details/157615246#includebits/stdc.h using namespace std; const int maxn1e85; bool st[maxn]; //isPrime int p[maxn]; //prime int cnt; void e_sieve(int n) { //eratosthenes_sieve memset(st,true,sizeof st); st[0]st[1]false; for(int i2; i*in; i) { if(!st[i]) continue; for(int ji*i; jn; ji) st[j]false; } for(int i2; in; i) { if(st[i]) p[cnt]i; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q,k; cinnq; e_sieve(n); while(q--) { cink; coutp[k]\n; } return 0; } /* in: 100 5 1 2 3 4 5 out: 2 3 5 7 11 */但是静态埃氏筛代码中定义了 maxn1e85对应的两个数组bool st[1e85]占用约 1e8 字节 ≈ 100MBint p[1e85]占用约 4*1e8 字节 ≈ 400MB总计约 500MB 内存这还只是 1e8 的情况。这在内存受限的情况下可能会导致MLEMemory Limit Exceeded内存超限。解决方法是vector替代全局静态数组核心是节省内存、提升灵活性、避免溢出。因此动态埃氏筛应运而生。● 那么在动态埃氏筛中如何对一个含 n 个元素的 bool 型的 vector 初始化为 true方法一创建 vector 的同时直接初始化为 true最常用例如vectorbool st(n, true);方法二vector 已存在需要将其重置为全 true例如st.assign(n, true);【算法代码动态埃氏筛】#includebits/stdc.h using namespace std; vectorbool st; //isPrime vectorint p; //prime void e_sieve(int n) { //eratosthenes_sieve st.assign(n1,true); //0~n st[0]st[1]false; for(int i2; i*in; i) { if(!st[i]) continue; for(int ji*i; jn; ji) st[j]false; } for(int i2; in; i) { if(st[i]) p.push_back(i); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q,k; cinnq; e_sieve(n); while(q--) { cink; coutp[k-1]\n; } return 0; } /* in: 100 5 1 2 3 4 5 out: 2 3 5 7 11 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/132352060https://blog.csdn.net/hnjzsyjyj/article/details/149666210https://blog.csdn.net/rstyduifudg/article/details/147163559https://www.luogu.com.cn/problem/solution/P3383