Miller-Rabin 素数测试

首先，总之，很玄学。

学过 \(a^{p-1}\equiv1\quad(mod\;p)\) 后，我们知道其逆定理不一定成立。

而对于 \(a^{p-1}\equiv1\quad(mod\;p)\) 成立但不是素数的 \(p\) ，称之为伪素数。

但是据统计（没错，就是暴力统计）后，我们发现对于每个 \(a\) ，伪素数个数大概都小于素数的 \(\frac 14\) 。即判错几率不很大。那么只要多测几组 \(a\) ，这个概率就超小了。这就是 \(Miller-Rabin\) 素数测试。

总之测前 \(17\) 个数就很保险了，\(1e15\) 范围内都是正确的。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef int int_;
#define int long long

int n;

int ksm(int x,int q,int p){
    int ret=1;
    while(q>0){
        if(q&1) ret=(ret*x)%p;
        x=(x*x)%p;
        q>>=1;
    }
    return ret;
}

bool check(int a,int x){
    int m=ksm(a,x-1,x);
    if(m==1) return false;
    else return true;
}


int_ main()
{
    scanf("%lld",&n);
    if(n<=16){
        if(n==2 || n==3 || n==5 || n==7 || n==11 || n==13 || n==17) printf("Yes");
        else printf("No");
        return 0;
    }
    for(int i=1;i<=17;i++){
        if(check(i,n)){
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}

• \(\frak by\;thorn\_\)