【bzoj3667】Rabin-Miller算法

2015年2月25日2,8253

Input

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

Output

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

Sample Input

6
2
13
134
8897
1234567654321
1000000000000

Sample Output

Prime
Prime
67
41
4649
5

HINT

数据范围:

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

题解

裸rho

卡常数丧心病狂

TAT

 

  • kd35okc2015年3月26日 下午5:37 回复

    黄学长泥的这个程序被我的同学随手卡掉了呀

    #1  
    • hzwer2015年3月26日 下午6:56 回复
      admin

      噢给个数据噜

      #11
  • AwD2016年2月6日 下午9:59 回复

    黄学长,这个rho没有跳出循环啊……陷入循环会炸的啊

    #2