題目描述
如題，給定一個范圍N，你需要處理M個某數字是否為質數的詢問（每個數字均在范圍1-N內）

輸入輸出格式
輸入格式：
第一行包含兩個正整數N、M，分別表示查詢的范圍和查詢的個數。

接下來M行每行包含一個不小于1且不大于N的整數，即詢問該數是否為質數。

輸出格式：
輸出包含M行，每行為Yes或No，即依次為每一個詢問的結果。

輸入輸出樣例
輸入樣例#1：
100 5
2
3
4
91
97
輸出樣例#1：
Yes
Yes
No
No
Yes
說明
時空限制：500ms 128M

數據規模：
對于30%的數據：N<=10000，M<=10000
對于100%的數據：N<=10000000，M<=100000

樣例說明：
N=100，說明接下來的詢問數均不大于100且不小于1。
所以2、3、97為質數，4、91非質數。
故依次輸出Yes、Yes、No、No、Yes。
.
.
.
.
.

程序：

#include<iostream> #include<cstring> using namespace std; int v[10000000],prime[10000000],n,m,p,a[10000000];void primes(int n) {memset(v,0,sizeof(v));m=0;for (int i=2;i<=n;i++){if (v[i]==0){v[i]=i;prime[++m]=i;}for (int j=1;j<=m;j++){if (prime[j]>v[i]||prime[j]>n/i) break;v[i*prime[j]]=prime[j];}}for (int i=1;i<=m;i++)a[prime[i]]=1; }int main() {cin>>n>>p;memset(a,0,sizeof(a));primes(n);for (int i=1;i<=p;i++){int x;cin>>x;if (a[x]==1) cout<<"Yes"<<endl; else cout<<"No"<<endl;}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10292857.html

總結

以上是生活随笔為你收集整理的洛谷 P3383 【模板】线性筛素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。