Miller_Rabin 算法 快速判断大质数（存在误差，非确定算法）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
ll mul(ll a,ll b) //高精度
{
    a%=mod;
    b%=mod;
    ll c=(long double)a*b/mod;
    ll ans=a*b-c*mod;
    return (ans%mod+mod)%mod;
}
ll pow_mod(ll x,ll n) //快速幂
{
    ll res=1;
    while(n)
    {
        if(n&1)
            res=mul(res,x);
        x=mul(x,x);
        n>>=1;
    }
    return res;
}
bool Miller_Rabin(ll x)
{
    if(x==2||x==7||x==61)
        return true;//要把所测试用的a先排除
    if(x%2==0||x==1)
        return false;
    mod=x;
    if(pow_mod(2,x-1)==1&&pow_mod(7,x-1)==1&&pow_mod(61,x-1)==1)
    {
        return true;
    }
    return false;
}

int main()
{
    for(ll i=1 ; i<50; i++)
        if(Miller_Rabin(i))
            printf("%lld ",i);

    return 0;
}