欧拉筛素数
2018-06-17 22:12:33来源:未知 阅读 ()
欧拉筛素数:
时间复杂度:O(n)
主要思路:对于每一个合数,让他的最大的约数把他筛去
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define lli long long int 6 using namespace std; 7 const int MAXN=10000001; 8 void read(int &n) 9 { 10 char c='+';int x=0;bool flag=0; 11 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 12 while(c>='0'&&c<='9') 13 x=(x<<1)+(x<<3)+c-48,c=getchar(); 14 flag==1?n=-x:n=x; 15 } 16 int n,m; 17 bool check[MAXN]; 18 int prime[MAXN]; 19 int tot=0; 20 int main() 21 { 22 read(n);read(m); 23 for(int i=2;i<=n;i++) 24 { 25 if(!check[i]) 26 prime[++tot]=i; 27 for(int j=1;j<=tot;j++) 28 { 29 if(i*prime[j]>n) 30 break; 31 check[i*prime[j]]=1; 32 if(!i%prime[j])// 前面已经用i*prime[j]把他能筛去的筛去, 33 //如果满足情况的话说明前面被筛过 34 break; 35 } 36 } 37 for(int i=1;i<=m;i++) 38 { 39 int q; 40 read(q); 41 if(q==1) 42 printf("No\n"); 43 else if(!check[q]) 44 printf("Yes\n"); 45 else 46 printf("No\n"); 47 } 48 return 0; 49 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:Brackets
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
- 「中山纪中集训省选组D2T1」书堆 欧拉常数 2019-08-16
- 简单的素数问题(C++) 2019-01-23
- 素数判定 2019-01-11
- PAT (Basic Level) Practice 1007 素数对猜想 2018-12-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash