关键词:
题目描述
如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)
输入输出格式
输入格式:
第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数,即询问概数是否为质数。
输出格式:
输出包含M行,每行为Yes或No,即依次为每一个询问的结果。
输入输出样例
100 5 2 3 4 91 97
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<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while (ch>=‘0‘ && ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } const int mxn=10000005; int pri[mxn*2],cnt; bool vis[mxn]; void PRI(int mxn) { vis[1]=1; int i,j; for (i=2;i<mxn;i++) { if (!vis[i]) pri[++cnt]=i; for (j=1;j<=cnt && i*pri[j]<mxn;j++) { vis[i*pri[j]]=1; if (i%pri[j]==0) break; } } return; } int n,m; int main() { n=read(); m=read(); PRI(n+3); int x; while (m--) { x=read(); if (vis[x]) printf("No "); else printf("Yes "); } return 0; }
线性筛洛谷p3383线性筛模板
思路:如果我们要筛出[1,n]内的所有素数,使用[1,√n]内的素数去筛就可以了设bool型数组a,a[i]表示i是否被某个素数筛过从2开始枚举每个数i:若a[i]=false,表示i没有更小的素因子,从而知道i是素数。枚举i的所有倍数j,令a[j]=1这... 查看详情
洛谷p3383模板线性筛素数
题目链接:https://www.luogu.org/problem/show?pid=3383题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式:第一行包含两个正整数N、M,分别表示查询的范围和查询的... 查看详情
p3383模板线性筛素数洛谷
https://www.luogu.org/problem/show?pid=3383#sub题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数... 查看详情
洛谷p3383模板线性筛素数
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情
洛谷p3383模板线性筛素数
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情
洛谷p3383模板线性筛素数(miller_rabin)
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情
[洛谷p3383]线性筛素数-欧拉筛法
Description如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)Input&OutputInput第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且不大于N的整数... 查看详情
p3383模板线性筛素数(代码片段)
P3383【模板】线性筛素数欧拉筛O(n)#include<iostream>#include<cstdio>usingnamespacestd;intn,m,cnt,prime[10000002],v[10000002];//prime:素数表v:存某数的最小质因数intmain()scanf("%d%d",&n,&m);for(inti=2;i< 查看详情
p3383模板线性筛素数
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式:第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且不大... 查看详情
p3383模板线性筛素数
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情
p3383模板线性筛素数(代码片段)
//P3383【模板】线性筛素数#include<bits/stdc++.h>usingnamespacestd;intis_prime[10000005];voidFind_prime(intn)memset(is_prime,1,sizeof(is_prime));is_prime[1]=0;for(inti=2;i*i<=n;i++)if(is_prime[i])for(intj=i*i;j<=n;j+=i)is_prime[j]=0;intmain()intn,m;scanf("%d%d",&n,&m);Fin... 查看详情
p3383模板线性筛素数(代码片段)
P3383【模板】线性筛素数埃氏筛->欧拉筛普通埃氏筛(O(nlognlogn))for(inti=2;i<=n;i++)//注意终止条件if(!notpri[i])for(intj=2;j*i<=n;j++)notpri[i*j]=true;优化for(inti=2;i<=n;i++)//到根号if(!notpri[i])for(intj=i;j*i<=n;j++)//j从i开始,因为... 查看详情
p3383模板线性筛素数(代码片段)
题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入输出格式输入格式: 第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情
普及组模板——线性筛素数
题目:【模板】线性筛素数(洛谷_3383)#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>usingnamespacestd;inlineintread(){intt=1,num=0;charc=getchar();w 查看详情
(模板)线性筛素数
————————————————————————————&mda 查看详情
线性筛素数模板
传送门:线性筛素数 Prime:1#include<cstdio>23constintMAXN=10000100;4intPrime[MAXN],n,m,Size;5boolVis[MAXN]={1,1};67intmain()8{9scanf("%d%d",&n,&m);10for(inti=2;i<n;i++)11{12if(!Vis[i])13Pr 查看详情
模板线性筛素数
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;intn,m,vis[10000010],prime[5000010],tot;voidinit(){for(inti=2;i<=n;i++){if(!vis[i])pr 查看详情
模板线性筛求素数(代码片段)
线性筛求素数1#include<iostream>2#include<cstring>3#include<algorithm>4#include<cstdio>56constintMAX_N=10000000+10;78boolvis[MAX_N];9intPrime[MAX_N>>1];10inlinevoidGetPrime(intn 查看详情