英语翻译原题：Prime text Description Given a big integer number,you

英语翻译
原题：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

素数判断用miller法 分解用pollard法 关键有几点 1:用2分法作64位乘法必须用unsigned __Int64 否则位移的时候会带符号(符号位移不掉) 2:pollard会陷入死循环 所以要加卡时 如果超过多少次还没出来就return 1,换个初始数继续 3:所有号必须全部加括号 像b1=(x32这种等号后面没加括号的是错误的 应该是b1=((x32); 4:发现pollard算法中用x*x-1产生随机数,如果那个-1改成其他数 效率会不一样 根据frkstyc大牛的代码 x*x+16381要将近快一倍 #include #include #include #define gcc 10007 //不同情况有不同的效果 #define MAX ((Int)1>= 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; }