[ZJU1517] 素数问题

    xiaoxiao2021-03-26  20


    题目描述

    给一个数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; }
    转载请注明原文地址: https://ju.6miu.com/read-600035.html

    最新回复(0)