#P3667. Rabin-Miller算法

    ID: 2864 传统题 6000ms 512MiB 尝试: 2073 已通过: 292 难度: 7 上传者: 标签>CF2200提高+/省选-Miller–RabinPollard–Rho快速乘防溢出快速幂欧几里得算法分治算法

Rabin-Miller算法

## 题目描述 给定若干整数。对每个整数判断它是否为质数。如果它是合数,求出它的最大质因子。 ## 输入格式 第一行一个整数 $T$,表示测试组数。接下来 $T$ 行,每行一个整数 $n$。 ## 输出格式 每组输出一行。若 $n$ 是质数,输出 `Prime`,否则输出它的最大质因子。 ## 数据范围 $1\le T\le350$。本站评测保证 $2\le n\le2^{63}-1$。 ```input1 6 2 13 134 8897 1234567654321 1000000000000 ``` ```output1 Prime Prime 67 41 4649 5 ```