首页 > 代码库 > [51nod1106]质数检测
[51nod1106]质数检测
解题关键：
根据质数的定义，在判断一个数n是否是质数时，我们只要用1至n-1去除n，看看能否整除即可。但我们有更好的办法。先找一个数m，使m的平方大于n，再用<=m的质数去除n（n即为被除数），如果都不能整除，则n必然是质数。如我们要判断1993是不是质数，50*50>1993，那么我们只要用1993除以<50的质数看是否能整除，若不能即为质数.
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int n,t; 5 int is_prime[100005],prime[100005]; 6 int sieve(int n){ 7 int p=0; 8 fill(is_prime,is_prime+n+1,1); 9 is_prime[0]=is_prime[1]=0;10 for(int i=2;i<=n;i++){11 if(is_prime[i]){12 prime[p++]=i;13 for(int j=2*i;j<=n;j+=i) is_prime[j]=0;14 }15 }16 return p;17 }18 int main(){19 cin>>t;20 int p=sieve(1e5);21 while(t--){22 bool flag=false;23 cin>>n; 24 if(n==2){25 printf("yes\n");26 continue;27 }28 for(int i=0;prime[i]*prime[i]<=n;i++){29 if(n%prime[i]==0){30 flag=true;31 break;32 }33 }34 if(flag) printf("no\n");35 else printf("yes\n");36 }37 return 0;38 }
[51nod1106]质数检测
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。