---

题目描述

给一个数n，要判断n是否为素数？

---

输入格式

输入有多组，每组占一行包含一个整数n(2<=n<=10^14)。

---

输出格式

如果n是素数输出“Yes”，否则输出“No”。

---

样例数据

样例输入

2 13 16 107

样例输出

Yes Yes No Yes

---

题目分析

Miller_Rabin

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> #include<ctime> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } long long Quick_Pow(long long a,long long b,long long mod) { if(b==0)return 1; else if(b==1)return a; else if(b%2==1)return ((Quick_Pow(a,b/2,mod)%mod)*(Quick_Pow(a,b/2,mod)%mod)*a%mod)%mod; else return ((Quick_Pow(a,b/2,mod)%mod)*(Quick_Pow(a,b/2,mod)%mod))%mod; } bool Miller_Rabin(long long n) { long long a; srand((unsigned)time(NULL)); for(long long i=1; i<=20; i++) { a=rand()%(n-1)+1; //若n是质数,且a,n互质,则a^(n-1)≡1(mod n) if(Quick_Pow(a,n-1,n)!=1)return false; } return true; } long long n; int main() { while(scanf("%lld",&n)!=EOF) { if(Miller_Rabin(n))puts("Yes"); else puts("No"); } return 0; }

---