#include<stdio.h>
#include<stdlib.h>
#include<time.h>
long long fac[100];
long long mod(long long a, long long b, long long n)
{
	long long t = 1, y = a;
	while(b) {
		if(b&1) t = (t * y) % n;
		y = (y*y) % n;
		b >>= 1;
	}
	return t;
}

long long F(long long x, long long n)
{
	long long t = x, tmp = x, ans = 0;
	while(t) {
		if(t & 1)
			ans = (ans + tmp) % n;
		tmp <<= 1; tmp %= n;
		t >>= 1;
	}
	return ans;
}

bool miller(long long n, long long b)
{
	long long l, m, i, x0, x1;
	m = n-1;
	l = 0;
	while(m % 2 == 0) {
		l++; m >>= 1;
	}
	x0 = mod(b, m, n);
	for(i = 0; i < l; i++) {
		x1 = F(x0, n);
		if ( x1 == 1 && x0 != 1 && x0 != n - 1 ) return 0;
		x0 = x1;
	}
	if(x1 != 1) return 0;
	return 1;
}
bool check(long long n)
{
	srand(time(0));
	if (n==1||(n!=2&&!(n%2))||(n!=3&&!(n%3))||(n!=5&&!(n%5))||(n!=7&&!(n%7))) return 0;
	if(n == 2) return 1;
	int time = 32;
	long long b;
	while(time--) {
		b = rand()%(n-1) + 1;
		if(!miller(n, b)) return 0;
	}
	return 1;
}

long long gcd(long long a, long long b)
{
	if(a < 0) a = -a;
	long long  r = a % b;
	while(r) {
		a = b; b = r;
		r = a % b;
	}
	return b;
}

long long pollard_brent(long long n)
{
	srand(time(0));
	long long x = 0, y, k = 2, i = 1, d = 1, a;
	a = 1;
	x = rand()%(n-1) + 1;
	y = x;
	while(true) {
		i++;
		x = (F(x, n) + n -1) % n;
		d = gcd(y-x, n);
		if(1 < d && d < n) return d;
		if(d == n || y == x) return n;
		if(k == i) {
			y = x;
			k <<= 1;
		}
	}
}
void find(long long n)
{
	if(check(n)) {
		fac[0]++;
		fac[fac[0]] = n;
		return ;
	}
	long long p = n;
	while(p == n)
		p = pollard_brent(p);
	find(p);
	find(n/p);
}

int main()
{
	long long n, t, i, tmp;

	scanf("%lld", &t);
	while(t--) {
		scanf("%lld", &n);
		if(check(n)) printf("Prime\n");
		else {
			if(!(n & 1) ) { printf("2\n"); continue;}
			fac[0] = 0;
			find(n);
			for(tmp = n, i = 1; i <= fac[0]; i++)
				if(fac[i] < tmp) tmp = fac[i];
			printf("%lld\n", tmp);
		}
	}
	return 0;
}

• Re:过掉了，居然是因为mod函数计算的时候可能会数据溢出导致程序判定一个素数为合数，而分解因式的时候找不到解导致的死循环。跑了将近4秒，什么效率呀 (0) fanliqian 2009-04-27 12:27:16