基本的判素都比較慢，對(duì)于這個(gè)題目的BT數(shù)據(jù)量(2 ^ 31)，也只能用概率判素模型了。
Miller-Rabin基于費(fèi)馬小定理：如果(a, p) = 1，那么a ^ (p - 1) = 1 mod p。滿足這個(gè)性質(zhì)的p叫偽素?cái)?shù)，如果一個(gè)數(shù)是偽素?cái)?shù)，那么它有很大可能是素?cái)?shù)。通過多次的枚舉a，利用快速冪取模判斷，就可以知道p是不是素?cái)?shù)，Miller-Rabin測(cè)試的成功率在3/4。
費(fèi)馬小定理是該定理的特殊形式：如果p是素?cái)?shù)，那么對(duì)于任意整數(shù)a：a ^ p = a mod p。這個(gè)定理可以用歸納法證明，證明依據(jù)這樣一個(gè)事實(shí)：組合數(shù)C(n, k)是一個(gè)整數(shù)，如果n是素?cái)?shù)，那么n和k!、(n - k)!的每一項(xiàng)都互素，可以提出n，也就是C(n, k) / n也是整數(shù)，所以n | C(n, k)。
這個(gè)題目的代碼如下：
#include <cstdio>
#include <stdlib.h>
const int MAX = 4, N = 1000000;
long long PowerMod(long long a, long long b, long long k)
{
long long ret = 1, f = a;
while (b)
{
if (b & 1)
ret = ret * f % k;
f = f * f % k;
b >>= 1;
}
return ret;
}
bool MillerRabin(long long n)
{
int i;
long long tmp;
srand(100);
for (i = 0; i < MAX; i++)
{
tmp = rand() % (n - 1) + 1;
if (PowerMod(tmp, n - 1, n) != 1)
break;
}
return (i == MAX);
}
int main()
{
long long n, i, j;
bool tag[N] = {1, 1, 0};
for (i = 2; i * i < N; i++)
{
if (tag[i]) continue;
for (j = i; j * i < N; j++)
tag[j*i] = 1;
}
while (scanf("%lld", &n) == 1)
{
if (n < N)
printf("%s\n", tag[n] ? "NO" : "YES");
else
printf("%s\n", ((n & 1) == 0) || !MillerRabin(n) ? "NO" : "YES");
}
return 0;
}