51nod 1106 质数检测(miller rabin 素数测试.)

基准时间限制：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示例

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}

相关文章