『算法-ACM 竞赛-数学-数论』Miller_Rabin 判断素数

ACM 常用模板合集

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int times = 10;
ll fast_mod(ll a,ll b,ll mod)//计算2^q的过程
{
    ll res = 0;
    while(b){
        if(b & 1) res = res + a;
        a <<= 1;
        if(a >= mod) a -= mod;
        if(res >= mod) res -= mod;
        b >>= 1;
    }
    return res;
}
ll fast_pow_mod(ll a,ll b,ll mod)//快速幂算出a^m
{
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
bool check(ll a,ll m,ll p,ll n)//对于每次随机的a进行测试
{
    ll temp = fast_pow_mod(a,m,n),ret = temp;
    for(int i = 0;i < p;++i){
        ret = fast_mod(temp,temp,n);
        if(ret == 1 && temp != n - 1 && temp != 1) return true;
        temp = ret;
    }
    return ret != 1;
}
bool Miller_Pabin(ll n)//Miller测试的主体结构
{
    if(n < 2) return false;
    if(n == 2) return true;
    if(n & 1 == 0) return false;//对于偶数的优化
    ll p = 0,x = n - 1;//p为Miller测试的q，x为Miller测试的m
    while(x & 1 == 0){
        x >>= 1;
        p++;
    }
    srand(time(NULL));
    for(int i = 0;i < times;++i){
        ll o = rand() % (n - 1) + 1;//o就是Miller测试的底数a
        if(check(o,x,p,n)) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        cout << (Miller_Pabin(n) ? "Prime" : "Not a Prime") << endl;
    }
    return 0;
}