传送门：POJ 1811 - Prime Test

题目大意：

给你一个数 $N$ $(2\leqslant N\leqslant 2^{54})$ 判断 $N$是否为素数，是的话直接输出 “Prime”，不是的话输出最小质因数。

解题思路：

看到这个数据范围，我就知道，常规算法肯定是行不通了=。=！所以就得用Miller-Rabin素数测试来判断是否是素数了，然后如果是的话，直接输出”Prime”就行了，不是就用Pollard rho整数分解方法算质因数，再找出所有质因数中最小的那一个就好了。要注意的地方也就是在进行Miller-Rabin素数测试的时候，要使用二次探测定理，排除卡迈克尔数（一个合数 $n$，若对所有满足 $gcd(b,n)=1$ 的正整数 $b$ 都有 $b^{n-1}\equiv 1\pmod n​$ 成立，则称之为卡迈克尔数），因为卡迈克尔数会导致素数测试结果出错。

通过代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 1000;
const int N = 5; // 测试次数
const int C = 200; // 指定 find() 函数参数2
int T;
ll factor[maxn], cnt;	// 素因子和素因子的数目，下标从 1 开始
ll mini, m;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll random(ll n)
{
    return (ll)((double)rand() / RAND_MAX * n + 0.5);
}
ll multi(ll a, ll b, ll m) // a * b % m
{
    ll ret = 0;
    while (b)
    {
        if (b & 1)
            ret = (ret + a) % m;
        b >>= 1;
        a = (a << 1) % m;
    }
    return ret;
}
ll quick_mod(ll a, ll b, ll m)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = multi(ans, a, m);
        b >>= 1;
        a = multi(a, a, m);
    }
    return ans;
}
bool Witness(ll a, ll n)
{
    ll m = n - 1;
    int j = 0;
    while (!(m & 1))
    {
        ++j;
        m >>= 1;
    }
    ll x = quick_mod(a, m, n);
    if (x == 1 || x == n - 1)
        return false;
    while (j--)
    {
        x = x * x % n;
        if (x == n - 1)
            return false;
    }
    return true;
}
bool miller_rabin(ll n)
{
    if (n == 2)
        return true;
    if (n < 2 || !(n & 1))
        return false;
    for (int i = 1; i <= N; ++i)
    {
        ll a = random(n - 2) + 1;
        if (Witness(a, n))
            return false;
    }
    return true;
}
ll pollard_rho(ll n, int c)
{
    ll x, y, d, i = 1, k = 2;
    x = random(n - 1) + 1;
    y = x;
    while (true)
    {
        ++i;
        x = (multi(x, x, n) + c) % n;
        d = gcd(y - x, n);
        if (1 < d && d < n)
            return d;
        if (y == x)
         	return n;
        if (i == k)
        {
            y = x;
            k <<= 1;
		}
    }
}
void find(ll n, int k)
{
    if (n == 1)
        return ;
    if (miller_rabin(n))
    {
        factor[++cnt] = n;
		mini = min(n, mini);
        return ;
    }
    ll p = n;
    while (p >= n)
        p = pollard_rho(p, k--);
    find(p, k);
    find(n / p, k);
}
int main(void)
{
    cin >> T;
    while (T--)
    {
        cin >> m;
        if (miller_rabin(m))
            cout << "Prime" << endl;
        else
        {
            mini = __LONG_LONG_MAX__;
            find(m, C);
            cout << mini << endl;
        }
    }
    return 0;
}