收藏
关注给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。
Input
第1行：一个数N，表示正整数的数量。(1 <= N <= 1000) 第2 - N + 1行：每行1个数(2 <= S[i] <= 10^9)
Output
输出共N行，每行为 Yes 或 No。
Input示例
5 2 3 4 5 6
Output示例
Yes Yes No Yes No
miller rabin 素数测试...
1 /************************************************************************* 2 > File Name: code/51nod/1106.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年10月19日 星期一 18时51分06秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<iomanip> 10 #include<cstdio> 11 #include<algorithm> 12 #include<cmath> 13 #include<cstring> 14 #include<string> 15 #include<map> 16 #include<set> 17 #include<queue> 18 #include<vector> 19 #include<stack> 20 #include<cctype> 21 22 #define yn hez111qqz 23 #define j1 cute111qqz 24 #define ms(a,x) memset(a,x,sizeof(a)) 25 using namespace std; 26 const int dx4[4]={1,0,0,-1}; 27 const int dy4[4]={0,-1,1,0}; 28 typedef long long LL; 29 typedef double DB; 30 const int inf = 0x3f3f3f3f; 31 32 bool witness(LL a,LL n) 33 { 34 LL t,d,x; 35 d=1; 36 int i=ceil(log(n-1.0)/log(2.0)) - 1; 37 for(;i>=0;i--) 38 { 39 x=d; d=(d*d)%n; 40 if(d==1 && x!=1 && x!=n-1) return true; 41 if( ((n-1) & (1<<i)) > 0) 42 d=(d*a)%n; 43 } 44 return d==1? false : true; 45 } 46 bool miller_rabin(LL n) 47 { 48 if(n==2) return true; 49 if(n==1 || ((n&1)==0)) return false; 50 for(int i=0;i<50;i++){ 51 LL a=rand()*(n-2)/RAND_MAX +1; 52 if(witness(a, n)) return false; 53 } 54 return true; 55 } 56 int main() 57 { 58 59 int n,cnt; 60 LL a; 61 while(scanf("%d",&n)!=EOF) 62 { 63 cnt=0; 64 while(n--) 65 { 66 scanf("%lld",&a); 67 if(miller_rabin(a)) 68 puts("Yes"); 69 else 70 puts("No"); 71 } 72 // printf("%d ",cnt); 73 } 74 return 0; 75 }