ll random(ll n)

{

    return (ll)((double)rand()/RAND_MAX*n + 0.5);

}

ll pow_mod(ll a,ll p,ll n)

{

    if(p == )

        return ;

    ll ans = pow_mod(a,p/,n);

    ans = ans*ans%n;

    if(p%)

        ans = ans*a%n;

    return ans;

}

bool Witness(ll a,ll n)

{

    ll m = n-;

    int j = ;

    while(!(m&))

    {

        j++;

        m >>= ;

    }

    ll x = pow_mod(a,m,n);

    if(x ==  || x == n-)

        return false;

    while(j--)

    {

        x = x*x%n;

        if(x == n-)

            return false;

    }

    return true;

}

bool Miller_Rabin(ll n)

{

    if(n < )

        return false;

    if(n == )

        return true;

    if(!(n&))

        return false;

    for(int i=;i<=;i++)   //5次测试

    {

        ll a = random(n-)+;

        if(Witness(a,n))

            return false;

    }

    return true;

}

int main()

{

    srand(time(NULL));

}