Prime Test Time Limit: 6000MSMemory Limit: 65536K Total Submissions: 29925Accepted: 7631 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 < 254). 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
2 5 10 Sample Output
Prime 2 Source
POJ Monthly
直接套bin神的板子。
;S = mult_mod(b, long long c){a %= c;b %= c;long long ret = 0;while (b){if (b & 1){ ret += a; ret %= c; }a <<= 1;if (a >= c)a %= c;b >>= 1;}return ret;}pow_mod(n, long long mod)//x^n%c{if (n == 1)return x%mod;x %= mod;long long tmp = x;long long ret = 1;while (n){if (n & 1) ret = mult_mod(ret, tmp, mod);tmp = mult_mod(tmp, tmp, mod);n >>= 1;}return ret;}check(n, t){long long ret = pow_mod(a, x, n);long long last = ret;for (int i = 1; i <= t; i++){ret = mult_mod(ret, ret, n);if (ret == 1 && last != 1 && last != n – 1) return true;//合数last = ret;}if (ret != 1) return true;return false;}Miller_Rabin(long long n){if (n<2)return false;if (n == 2)return true;x = n – 1;long long t = 0;while ((x & 1) == 0){ x >>= 1; t++; }for (int i = 0; i<S; i++){(check(a, n, x, t))return false;//合数}return true;}factor[gcd(b){(a<0) return gcd(-a, b);while (b){long long t = a%b;a = b;b = t;}return a;}Pollard_rho(c){long long i = 1, k = 2;long long x0 = rand() % x;long long y = x0;while (1){i++;x0 = (mult_mod(x0, x0, x) + c) % x;long long d = gcd(y – x0, x);if (d != 1 && d != x) return d;if (y == x0) return x;if (i == k){ y = x0; k += k; }}}n){if (Miller_Rabin(n))//素数{factor[tol++] = n;return;}long long p = n;while (p >= n)p = Pollard_rho(p, rand() % (n – 1) + 1);findfac(p);findfac(n / p);}int main(){// srand(time(NULL));//需要time.h头文件 //POJ上G++要去掉这句话int T;long long n;scanf(“%d”, &T);while (T–){scanf(“%I64d”, &n);if (Miller_Rabin(n)){printf(“Prime\n”);continue;}tol = 0;findfac(n);long long ans = factor[0];for (int i = 1; i<tol; i++)if (factor[i]<ans)ans = factor[i];printf(“%I64d\n”, ans);}return 0;}
，做对的事情比把事情做对重要。
