基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
给出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))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31
32bool witness(LL a,LL n)
33{
34LL t,d,x;
35d=1;
36int i=ceil(log(n-1.0)/log(2.0)) - 1;
37for(;i>=0;i--)
38{
39x=d; d=(d*d)%n;
40if(d==1 && x!=1 && x!=n-1) return true;
41if( ((n-1) & (1<<i))> 0)
42d=(d*a)%n;
43}
44return d==1? false : true;
45}
46bool miller_rabin(LL n)
47{
48if(n==2) return true;
49if(n==1 || ((n&1)==0)) return false;
50for(int i=0;i<50;i++){
51LL a=rand()*(n-2)/RAND_MAX +1;
52if(witness(a, n)) return false;
53}
54return true;
55}
56int main()
57{
58
59int n,cnt;
60LL a;
61while(scanf("%d",&n;)!=EOF)
62{
63cnt=0;
64while(n--)
65{
66scanf("%lld",&a);
67if(miller_rabin(a))
68puts("Yes");
69else
70puts("No");
71}
72// printf("%dn",cnt);
73}
74return 0;
75}