POJ 1811 Prime Test（大素数判断+大合数素因子分解）

题意:判断n（n<2^54）是否为素数，如果不是，那么输出n最小的因子。

思路：这题肯定不能用普通的枚举来做，

对于判断大素数，可以用Miller_Rabin随机算法进行素性检验，而分解素因数可以使用Miller_Rabin搭配Pollard_rho算法进行分解，Miller_Rabin算法出错的概率小于2^(-s)，s为测试的数据个数，如果不放心的话可以多试几组，在实际应用中是一种很好的随机化算法，Pollard_rho算法理论复杂度在O（n^(1/4)）左右，实际中表现也很好，

ps：看了算法导论好久.....终于弄懂，整理了一个模板。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define LL long long
#define pii pair<int,int>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;

const int maxn = 10000 + 5;
const int S = 20;
LL factor[maxn];
int tot;
LL multi_mod(LL a,LL b,LL c) {
	a %= c; b %= c;
	LL ret = 0;
	while(b) {
		if(b&1) {
			ret += a;
			if(ret >= c) ret -= c;
		}
		a <<= 1; b >>= 1;
		if(a >= c) a-=c;		
	}
	return ret;
}
//返回a^p mod n,要求0 <= a < n
LL pow_mod(LL a,LL p,LL n) {
	if(p == 0) return 1;
	LL ans = pow_mod(a,p/2,n);
	ans = multi_mod(ans,ans,n);
	if(p&1) ans = multi_mod(ans,a,n);
	return ans;
}
//判断n是否是合数，是的话返回1，否则返回0 
bool check(LL a,LL n,LL x,LL t) {//以a为基，n-1=x*2^t，检验n是不是合数 
	LL ret = pow_mod(a,x,n);
	if(ret==n-1 || ret==1) return 0; 
	for(int i = 1; i < t; i++) {
		ret = multi_mod(ret,ret,n);
		if(ret == 1) return 1;
		if(ret == n-1) return 0;
	}
	return 1; 
}
bool Miller_Rabin(LL n) {
	LL x = n - 1,t = 0;  
	while(!(x&1)) x >>=1,t++;
	bool flag = 1;
	if(t>=1) {
		for(int k = 0; k < S; k++) {
			LL a = rand()%(n-1) + 1;
			if(check(a,n,t)) {
				flag = 1; break;
			}
			flag = 0;
		}
	}
	if(!flag || n==2) return 0;
	return 1;
}
LL gcd(LL a,LL b) {
    if (a==0) return 1;
    if (a<0) return gcd(-a,b);
    while (b){
        LL t=a%b; a=b; b=t;
    }
    return a;
}

LL Pollard_rho(LL x,LL c) {
    LL i=1,x0=rand()%x,y=x0,k=2;
    while (1){
        i++;
        x0=(multi_mod(x0,x0,x)+c)%x;
        LL d=gcd(y-x0,x);
        if (d!=1 && d!=x){
            return d;
        }
        if (y==x0) return x;
        if (i==k){
            y=x0;
            k+=k;
        }
    }
}
void findfac(LL n) {           //递归进行质因数分解N
    if (!Miller_Rabin(n)){
        factor[tot++] = n;
        return;
    }
    LL p=n;
    while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1);
    findfac(p);
    findfac(n/p);
}


int main() {
    //freopen("input.txt","r",stdin);
	srand(time(NULL));
	int T; cin >> T;
	while(T--) {
		LL n; cin >> n;
		if(!Miller_Rabin(n)) {
			puts("Prime"); continue;
		}
		tot = 0;
		findfac(n);
		LL ans = factor[0];
		for(int i = 1; i < tot; i++) if(factor[i]<ans) ans = factor[i];
		cout << ans << endl;	
	}
    return 0;
}