poj 1811 Prime Test 大数素数测试+大数因子分解-白红宇

poj 1811 Prime Test 大数素数测试+大数因子分解

阅读量：7100 次

发布时间：2019-06-28

本文共 2960 字，大约阅读时间需要 9 分钟。

Prime Test

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 27129		Accepted: 6713
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

⁵⁴).

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

Sample Output

Prime2

Source

1 /*  2 给你一个大数，如果是素数输出prime，如果不是，则输出其最小的质因子。  3   4 利用Miller-Rabbin素数测试和Pollar-rho因数分解可以AC这道题  5   6 */  7   8   9 #include
      
        10 #include
       
         11 #include
        
          12 #include
         
           13 #include
          
            14 using namespace std; 15  16 typedef __int64 LL; 17 //**************************************************************** 18 // Miller_Rabin 算法进行素数测试 19 //速度快，而且可以判断 <2^63的数 20 //**************************************************************** 21 const int S=20;//随机算法判定次数，S越大，判错概率越小 22  23  24 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63 25 { 26     a%=mod; 27     b%=mod; 28     LL ans=0; 29     while(b) 30     { 31         if(b&1) 32         { 33             ans=ans+a; 34             if(ans>=mod) 35             ans=ans-mod; 36         } 37         a=a<<1; 38         if(a>=mod) a=a-mod; 39         b=b>>1; 40     } 41     return ans; 42 } 43  44 LL pow_mod(LL a,LL b,LL mod) // a^b%mod 45 { 46     LL ans=1; 47     a=a%mod; 48     while(b) 49     { 50         if(b&1) 51         { 52             ans=mult_mod(ans,a,mod); 53         } 54         a=mult_mod(a,a,mod); 55         b=b>>1; 56     } 57     return ans; 58 } 59  60 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数 61 //一定是合数返回true,不一定返回false 62  63 bool check(LL a,LL n,LL x,LL t) 64 { 65     LL ret=pow_mod(a,x,n); 66     LL last=ret; 67     for(int i=1;i<=t;i++) 68     { 69         ret=mult_mod(ret,ret,n); 70         if(ret==1 && last!=1 && last!=n-1) return true;//合数 71         last=ret; 72     } 73     if(ret!=1) return true; 74     else return false; 75 } 76  77 // Miller_Rabin()算法素数判定 78 //是素数返回true.(可能是伪素数，但概率极小) 79 //合数返回false; 80  81 bool Miller_Rabin(long long n) 82 { 83     if(n<2)return false; 84     if(n==2) return true; 85     if( (n&1)==0) return false;//偶数 86     LL x=n-1; 87     LL t=0; 88     while( (x&1)==0 ) { x>>=1;t++;} 89     for(int i=0;i
           
            =n)145 p=Pollard_rho(p,rand()%(n-1)+1);146 findfac(p);147 findfac(n/p);148 }149 150 int main()151 {152 // srand(time(NULL));//需要time.h头文件 //POJ上G++要去掉这句话153 int T;154 LL n;155 scanf("%d",&T);156 while(T--)157 {158 scanf("%I64d",&n);159 if(Miller_Rabin(n))160 {161 printf("Prime\n");162 continue;163 }164 tol=0;165 findfac(n);// 对n的素数分解166 LL ans=factor[0];167 for(int i=1;i