【模板】Pollard-Rho
题目描述
Miller Rabin 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法,但是在选择多种底数的情况下,正确率是可以接受的。
Pollard rho 是一个非常玄学的方式,用于在 $O(n^{1/4})$ 的期望时间复杂度内计算合数 $n$ 的某个非平凡因子。事实上算法导论给出的是 $O(\sqrt p)$,$p$ 是 $n$ 的某个最小因子,满足 $p$ 与 $n/p$ 互质。但是这些都是期望,未必符合实际。但事实上 Pollard rho 算法在实际环境中运行的相当不错。
这里我们要写一个程序,对于每个数字检验是否是质数,是质数就输出 `Prime`;如果不是质数,输出它最大的质因子是哪个。
输入输出格式
输入格式
第一行,$T$ 代表数据组数(不大于 $350$)
以下 $T$ 行,每行一个整数 $n$,保证 $2 \le n \le {10}^{18}$。
输出格式
输出 $T$ 行。
对于每组测试数据输出结果。
输入输出样例
输入样例 #1
6
2
13
134
8897
1234567654321
1000000000000
输出样例 #1
Prime
Prime
67
41
4649
5
说明
2018.8.14 新加数据两组,时限加大到 2s,感谢 @whzzt
2022.12.22 加入新的数据,感谢 @ftt2333 和 Library Checker
by @will7101