Prime Test
Time Limit: 6000MS
Memory Limit: 65536K
Total Submissions: 17747
Accepted: 3644
Case Time Limit: 4000MS
Description
Given a big integer number, you are required to find out whether it's a prime number.
Input
The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 2
54).
Output
For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.
Sample Input
2
5
10
Sample Output
Prime
2
この問題はmiilerです.rabin素数テストとpollard_rho質因子分解の標準テンプレート問題...初めてこのような问题をして、この问题は私はネット上の他の人のコードを参照して书いたので、学习として、テンプレートとして勉强しました.....
コード:
言語:c++
#include
#include using namespace std; long long factor[100],fac_top = -1;//2つの数のgcd long long gcd(long long a,long long b){if(a=0)return b;long long c;while(b!=0){c=b;b=a%b;a=c;}return a; }//ret = (a*b)%n (n<2^62) long long muti_mod(long long a,long long b,long long n) { long long exp = a%n, res = 0; while(b) { if(b&1) { res += exp; if(res>n) res -= n; } exp <<= 1; if(exp>n) exp -= n; b>>=1; } return res; }//ret = (a^b)%n long long mod_exp(long long a,long long p,long long m) { long long exp=a%m, res=1;//while(p>1) { if(p&1)//res=muti_mod(res,exp,m); exp = muti_mod(exp,exp,m); p>>=1; } return muti_mod(res,exp,m); }//miller-rabin法試験素数、time試験回数bool miller_rabin(long long n, long long times) { if(n==2)return 1; if(n<2||!(n&1))return 0; long long a, u=n-1, x, y; int t=0; while(u%2==0){ t++; u/=2; } srand(time(0)); for(int i=0;i= n) p = pollard_rho(p,k--);//k値変化、デッドサイクルfindFactor(p,k);findFactor(n/p,k); } int main() { long long t,n,min; cin>>t; while(t--) { cin>>n; fac_top = min = -1; if(miller_rabin(n,10)) cout<<"Prime"<