miller_rabin质数筛法

RP(Random polynomial)的时间复杂度

板子

/*
判断一个大整数是否为素数，基于 米勒-拉宾素性检验
input   :   long long 范围内的一个整数
output  :   true or flase
*/

#include <bits/stdc++.h>
using namespace std;
#define N 10
typedef long long LL;
LL random(LL n) {
    return (LL)((double)rand()/RAND_MAX*n+0.5);
}
LL multi(LL a,LL b,LL m) { //计算a*b%m
    LL ret=0;
    while(b) {
        if(b&1) ret=(ret+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return ret;
}
LL quick_mod(LL a,LL m) { //计算a^b%m
    LL ans=1;
    while(b) {
        if(b&1) {
            ans=multi(ans,a,m);
            b--;
        }
        b>>=1;
        a=multi(a,m);
    }
    return ans;
}
bool miller_rabin(LL n) {
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    LL m=n-1;
    int k=0;
    while((m&1)==0) {
        k++;
        m>>=1;
    }
    for(int i=0; i<N; i++) {
        LL a=rand()%(n - 1)+1;
        LL x=quick_mod(a,m,n);
        LL y=0;
        for(int j=0; j<k; j++) {
            y=multi(x,x,n);
            if(y==1&&x!=1&&x!=n-1) return false;
            x=y;
        }
        if(y!=1) return false;
    }
    return true;
}
int main() {
    LL n;
    int T;
    cin>>T;
    while(T--) {
        cin>>n;
        if(miller_rabin(n)) puts("Yes");
        else puts("No");
    }
    return 0;
}