Question

请acm高手做POJ里的c++题，题号1811，先中文翻译，写程序代码

原题： Prime text 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 < 2 54 ). 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

Answer 1

素数判断用miller法 分解用pollard法 关键有几点 1:用2分法作64位乘法必须用unsigned __Int64 否则位移的时候会带符号(符号位移不掉) 2:pollard会陷入死循环 所以要加卡时 如果超过多少次还没出来就return 1,换个初始数继续 3:所有<<号,>>号必须全部加括号 像b1=(x<<32)>>32这种等号后面没加括号的是错误的 应该是b1=((x<<32)>>32); 4:发现pollard算法中用x*x-1产生随机数，如果那个-1改成其他数 效率会不一样 根据frkstyc大牛的代码 x*x+16381要将近快一倍 #include <iostream> #include <cstdlib> #include <map> #define gcc 10007 //不同情况有不同的效果 #define MAX ((Int)1<<63)-1 using namespace std; typedef unsigned __int64 Int; Int p[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; map < Int, int > Map; inline Int Gcd(Int a, Int b) { Int m = 1; if(!b) return a; while(m) { m = a % b; a = b; b = m; } return a; } //计算a*b%n inline Int Produc_Mod(Int a, Int b, Int mod) { Int sum = 0; while(b) { if(b & 1) sum = (sum + a) % mod; a = (a + a) % mod; b >>= 1; } return sum; } //计算a^b%n inline Int Power(Int a, Int b, Int mod) { Int sum = 1; while(b) { if(b & 1) sum = Produc_Mod(sum, a, mod); a = Produc_Mod(a, a, mod); b >>= 1; } return sum; } //Rabin_Miller判素 bool Rabin_Miller(Int n) { int i, j, k = 0; Int u, m, buf; //将n-1分解为m*2^k if(n == 2) return true; if(n < 2 || !(n & 1)) return false; m = n-1; while(!(m & 1)) k++, m >>= 1; for(i = 0; i < 9; i++) { if(p[i] >= n) return true; u = Power(p[i], m, n); if(u == 1) continue; for(j = 0; j < k; j++) { buf = Produc_Mod(u, u, n); //看是否有非平凡因子存在 if(buf == 1 && u != 1 && u != n-1) return false; u = buf; } //如果p[i]^(n-1) % n != 1 那么 n为合数 if(u-1) return false; } return true; } //寻找n的一个因子 Int Pollard_rho(Int n) { int i = 1; Int x = rand() % (n-1) + 1; Int y = x; Int k = 2; Int d; do{ i++; d = Gcd(n + y - x, n); if(d > 1 && d < n) return d; if(i == k) y = x, k *= 2; x = (Produc_Mod(x, x, n) + n - gcc) % n; }while(y != x); return n; } Int Min; Int Pollard_Min(Int n) { Int p, a, b = MAX; if(n == 1) return MAX; if(Rabin_Miller(n)) return n; p = Pollard_rho(n); a = Pollard_Min(p); Int y = n / p; b = Pollard_Min(y); return a < b ? a : b; } int main() { int t, i; Int n; scanf("%d", &t); while(t--) { scanf("%I64d", &n); Min = MAX; if(Rabin_Miller(n)) printf("Prime\n"); else printf("%I64d\n", Pollard_Min(n)); } return 0; }