POJ 1811 Prime Test（ Pollard-rho整数分解经典题 ）

---

**链接：****传送门 **

题意：输入 n ，判断 n 是否为素数，如果是合数输出 n 的最素因子

思路：Pollard-rho经典题

---

/*************************************************************************

    > File Name: Pollard_rho_Test.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月24日 星期三 10时55分04秒

 ************************************************************************/

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstdlib>

using namespace std;

#define ll long long

#define TIME 30

const int MAX_N = 1000;

const int C = 201;

ll number = 0 , MIN ;

int List[MAX_N];

// --------------------Miller_Rabin素数测试-------------------------

ll RANDOM(ll n){ return (ll)((double)rand()/RAND_MAX * n + 0.5); }

ll quick_multi(ll a,ll b,ll Mod){	// 快速计算 a * b % Mod

	ll ret = 0;

	while(b){

		if(b&1)	ret = (ret + a) % Mod;

		a = ( a << 1 ) % Mod;

		b >>= 1;

	}

	return ret % Mod;

}

ll quick_pow(ll a,ll x,ll Mod){		// 快速计算 a^x % Mod

	ll ret = 1;

	while(x){

		if(x&1)	{ ret = quick_multi( ret , a , Mod); x--; }

		x >>= 1;

		a = quick_multi( a , a , Mod );

	}

	return ret % Mod;

}

bool Witness(ll a,ll n){	// Miller_Rabin 二次探测

	ll tmp = n - 1;

	int j = 0;

	while( !( tmp & 1 )  ){	tmp >>= 1; j++; }

	ll x = quick_pow( a , tmp , n );

	if( x == 1 || x == n-1 )	return false;

	while( j-- ){

		x = x*x % n ;

		if( x == n-1 )	return false;

	}

	return true;

}

bool Miller_Rabin(ll n){	// 检测n是否为素数

	if( n < 2 )		return false;

	if( n == 2 )	return true;

	if( !(n&1) )	return false;

	for(int i = 1 ; i <= TIME ; i++){

		ll a = RANDOM( n - 2 ) + 1;	// 得到随机底数

		if( Witness( a , n ) )		return false;

	}

	return true;

}

// --------------------Pollard_rho大整数分解-------------------------

ll gcd(ll a,ll b){	return b == 0 ? a : gcd( b , a%b ); }

ll Pollard_rho(ll n,ll c){	// 找到n的一个因子

	ll x , y , d , i = 1 , k = 2;

	x = RANDOM( n - 1 ) + 1;

	y = x;

	while(true){

		i++;

		x = ( quick_multi( x , x , n ) + c ) % n;

		d = gcd( y - x , n );

		if( 1 < d && d < n )	return d;

		if( y == x )			return n;

		if( i == k ){

			y = x;	k <<= 1;

		}

	}

}

void find(ll n,ll c){

	if( n == 1 )	return;

	if( Miller_Rabin(n) ){

		List[ number++ ] = n ;

		MIN = min( MIN , n );

		return;

	}

	ll p = n ;

	while( p >= n )	p = Pollard_rho( p , c-- );

	find( p , c );

	find( n/p , c );

}

int main(){

	int T;	ll tar , tmp = pow(2,54)-1;

	scanf("%d",&T);

	while(T--){

		scanf("%lld",&tar);

		if( Miller_Rabin(tar) )		printf("Prime\n");

		else{

			MIN = tmp;

			find( tar , C );

			printf("%lld\n",MIN);

		}

	}

	return 0;

}