Miller-Rabin 素性测试代码

• 之前的笔记中讲过这个算法，所以在这里把代码贴一下。

int prime[8] = {2, 3, 5, 7, 11, 13, 17, 37};

bool miller_rabin(int n, int a) {
    int d = n - 1, r = 0;
    while(d % 2 == 0)
        d = d >> 1, r++;
    int z = fastPower(a, d, n);
    if(z == 1) return true;
    for(int i = 0; i < r; i++) {
        if(z == n - 1) return true;
        z = 1ll * z * z % n;
    }
    return false;
}

bool check(int n) {
    if(n < 2) return false;
    for(int i = 0; i < 8; i++) {
        if(n == prime[i]) return true;
        if(n % prime[i] == 0) return false;
        if(!miller_rabin(n, prime[i])) return false;
    }
    return true;
}