基本的判素都比較慢，對于這個題目的BT數據量(2 ^ 31)，也只能用概率判素模型了。
Miller-Rabin基于費馬小定理：如果(a, p) = 1，那么a ^ (p - 1) = 1 mod p。滿足這個性質的p叫偽素數，如果一個數是偽素數，那么它有很大可能是素數。通過多次的枚舉a，利用快速冪取模判斷，就可以知道p是不是素數，Miller-Rabin測試的成功率在3/4。
費馬小定理是該定理的特殊形式：如果p是素數，那么對于任意整數a：a ^ p = a mod p。這個定理可以用歸納法證明，證明依據這樣一個事實：組合數C(n, k)是一個整數，如果n是素數，那么n和k!、(n - k)!的每一項都互素，可以提出n，也就是C(n, k) / n也是整數，所以n | C(n, k)。
這個題目的代碼如下：
#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;
}
posted on 2009-03-18 21:15
sdfond 閱讀(642)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory