基本的判素都比较慢，对于这个题目的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 阅读(619)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Number Theory