数论-Miller-Rabin素数测试

据说测试的数字 a 取素数比较好，当 a 取遍 [1, 50] 之间的素数（共 15 个）时，可以保证 long long 范围内没有差错。

测试题目：LOJ143 质数判定

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 #define SC(a, b) (static_cast<a>(b))
 7 
 8 typedef long long LL;
 9 typedef long double LD;
10 
11  LL test[16] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}, test_cnt = 15;
12 
13 LL mul(LL a, LL b, LL n)
14 {
15     LL t = a * b - SC(LL, SC(LD, a) * b / n + 0.5) * n;//注意这里 +0.5 非常重要！
16     return t < 0 ? t + n : t;
17 }
18 
19 LL mont(LL a, LL b, LL n)
20 {
21     LL t = 1;
22     a %= n;
23     while (b) {
24         if (b & 1) t = mul(t, a, n);
25         b >>= 1, a = mul(a, a, n);
26     }
27     return t;
28 }
29 
30 bool check(LL n)
31 {
32     if (n == 2) return true;
33     if (n < 2 || n & 1 ^ 1) return false;
34     LL d = n - 1, r = 0;// n-1 = d * 2^r
35     while (d & 1 ^ 1) d >>= 1, ++r;
36     for (int i = 1; i <= test_cnt; ++i) {
37         if (test[i] == n) return true;
38         LL a = test[i];
39         LL x = mont(a, d, n), y;
40         for (LL j = 1; j <= r; ++j) {
41             y = mul(x, x, n);
42             if (y == 1 && x != 1 && x != n-1) return false;
43             x = y;
44         }
45         if (x != 1) return false;
46     }
47     return true;
48 }
49 
50 int main()
51 {
52     LL n;
53     while (scanf("%lld", &n) != EOF) {
54         if (check(n)) printf("Y
");
55         else printf("N
");
56     }
57     return 0;
58 }