核心内容摘要
SciChart iOS/Android 图表库 v4.7 正式发布：移动数据可视化全面增强
【题目来源】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(n
return false; for(int i2; isqrt(n); i) { if(n%i
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(
; cout.tie(
; 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(