Miller Rabin

Miller Rabin是一种快速判定素数的方法，可以在log的时间内判断一个数是否为素数。

首先有两个引理：

1.费马小定理

2.二次探测

这两个引理对于素数均成立，而对于非素数则不一定成立，因此我们就根据这两个性质来排数掉非素数。显然这种方法有一定的错误机率，但是实测错误的机率非常低（脸黑不适合学信竞）。一般来说，我们取40以下的质数就行了。

算法流程：

首先运用费马小定理：若p为质数，a^p-1≡1(mod p)，这里的a就是我们上面说的要取的质数，同时根据二次探测定理，若p为质数，a^2≡1(mod p)，那么a≡1或n-1(mod p)，同时显然若a≡1(mod p)，那么a^2≡1(mod p)，这样算法的轮廓就逐渐出来了。

首先将p-1一直除以2，我们设得到的结果为t，算出a^t为k，对于k每次进行平方，若平方之后≡1(mod p)，那么如果之前mod p的余数不为1或n-1就返回false，同时当k一直乘到p-1之后mod p的余数仍然不为1的话，也返回false。这样当我们多取几个a（一般是40一下素数）判断一下，如果没有返回过false就返回true了。

最后，记得特判1，偶数也可以全部拉出来特判一次，是偶数就直接返回结果，可以省掉一些询问的时间。

如果还没懂就看代码吧:

long long c[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
inline bool Miller_Rabin(long long n)
{
    if (n == 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    long long p = n - 1;
    int k = 0;
    while (p % 2 == 0)
    {
        p /= 2;
        k++;
    }
    for (int i = 0; i < 12; ++i)
    {
        if (n == c[i])
            return true;
        long long num;
        num = ksm(c[i], p, n);
        if (num == 1)
            continue;
        for (int j = 1; j <= k; ++j)
        {
            long long nxt = qmul(num, num, n);
            if (nxt == 1 && num != 1 && num != n - 1)
                return false;
            num = nxt;
            if (num == 1)
                break;
        }
        if (num != 1)
            return false;
    }
    return true;
}