poj 1811 Prime Test-白红宇

poj 1811 Prime Test

阅读量：6671 次

发布时间：2019-06-25

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

这个题用到Miller_rabin与pallord算法：

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long long using namespace std;LL p[10] = { 2,3,5,7,11,13,17,19,23,29 };const LL Max = ( LL )1<<62;LL Multi( LL a ,LL b , LL n )//计算a*b { LL sum = 0; while( b ) { if( ( b&1 ) ) sum = ( sum + a )%n; a<<=1; b>>=1; if( a >= n ) a %= n; } return sum; }LL Quick_mod( LL a ,LL b ,LL n )//计算当d位奇数时a^b { LL sum = 1; while( b ) { if( ( b&1 ) ) sum = Multi( sum , a ,n ); a = Multi( a , a ,n ); b >>= 1; } return sum; }LL Miller_rabin( LL n )//米勒罗宾测试 { LL m = n -1,d,L; int k=0; if( n == 2 ) return true; if( n < 2 || !( n&1 )) return false; while( !( m&1 ) )//求n-1的2的次方 { k++ ; m >>= 1; } for( int i = 0 ; i < 9 ; i ++ ) { if( p[i] >= n ) return true; d = Quick_mod( p[i] , m ,n ); if( d == 1 ) continue; for( int j = 0; j < k ; j ++ ) { L = Multi( d , d ,n ); if( L == 1 && d != 1 && d != ( n- 1 ) ) return false; d = L; } if( d != 1 ) return false; } return true;}LL Gcd( LL a ,LL b ){ return b ==0 ? a : Gcd( b , a%b ); }LL Pallord( LL n ){ LL x,y,c=0,d,i=1,k=2; while(c==0 || c==2 ) c = abs( rand())%(n-1) + 1; x = y = (rand( )%( n-1 )) + 1; do { i++; d = Gcd( y + n - x, n ); if( d >1 && d < n ) return d; if( i == k ) { y = x; k <<= 1; } x = (Multi( x , x, n )+n-c )%n; }while( x != y ); return n; }LL Pallord_min( LL n ){ LL p,a,b; if( n == 1 ) return Max; if( Miller_rabin( n ) ) return n;//如果n为素数就返回 p = Pallord( n );//如果不是继续分解 a = Pallord_min( p );//继续分解p； b = Pallord_min( n / p ); return a < b ? a:b; //返回最小的质因子 }int main( ){ LL num; int Case; while( scanf( "%d",&Case )==1 ) { while( Case-- ) { scanf( "%I64d",&num ); if( Miller_rabin( num ) ) puts( "Prime" ); else printf( "%I64d\n",Pallord_min( num ) ); } } //system( "pause" ); return 0;}