我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的,当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用,如果需要判断k个较大的数字(\(n \le 10^{18}\))的数字,估计一下要运算\(k * 10^8\)之多,显然无法接受。
介绍 / Introduction
这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内进行对n的素性检验的方法,k是检验数的个数,一般在10以内,复杂度骤降。
作为竞赛使用不必深究其原理,感兴趣的可以看看这些文章:
Miller Rabin算法详解 - 自为风月马前卒 - 博客园 (cnblogs.com)
【朝夕的ACM笔记】数论-Miller Rabin素数判定 - 知乎 (zhihu.com)
基本原理就是费马检验 + 二次探测理论,当然这是一个随机算法,只是它在足够大的范围内准确度极高(接近100%)。
经过k次检测,判断素性的失败率小于\(\frac{1}{4^k}\),已经基本上可以认为是正确的了,至少在OI范围内不会出错。
例题:U148828 素数判断(Miller-Rabin模板) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板 / Templete
#define int long long // 为了方便下面的longlong都用int表示 int qmi(int a, int b, int p) // 快速幂 { int res = 1; while (b) { // 注意!中间结果可能溢出,需要使用__int128过渡 if (b & 1)res = (__int128)res * a % p; a = (__int128)a * a % p, b >>= 1; } return res; } bool isprime(int x)//Miller_Rabin { //特判 if (x < 3)return x == 2; if (x % 2 == 0)return false; //用下面这几个数字判断不会出错 int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0; while (d % 2 == 0)d >>= 1, ++r; for (auto a : A) { int v = qmi(a, d, x); if (v <= 1 || v == x - 1)continue; for (int i = 0; i < r; ++i) { v = (__int128)v * v % x; if (v == x - 1 && i != r - 1) { v = 1; break; } if (v == 1)return false; } if (v != 1)return false; } return true; }
Comments NOTHING