Rabin-Miller算法

时间限制:60s      空间限制:512MB

题目描述


输入格式

第一行:CAS,代表数据组数(不大于350),以下CAS行,每行一个数字,保证在64位长整形范围内,并且没有负数。你需要对于每个数字:第一,检验是否是质数,是质数就输出Prime
第二,如果不是质数,输出它最大的质因子是哪个。


输出格式

第一行CAS(CAS<=350,代表测试数据的组数)
以下CAS行:每行一个数字,保证是在64位长整形范围内的正数。
对于每组测试数据:输出Prime,代表它是质数,或者输出它最大的质因子,代表它是和数


样例输入

6 
2 
13 
134 
8897 
1234567654321 
1000000000000 

样例输出

Prime 
Prime 
67 
41 
4649 
5 

提示

数据范围:
保证cas<=350,保证所有数字均在64位长整形范围内。


题目来源

没有写明来源