判断一个数是否是素/质数

垃圾版本 对从2到n-1取模，不为0则是素数，O(N)

bool judge(ll n)
{
    if(n==2||n==3) return true;
    for(int i=2;i<n;i++)
        if(n%i==0) return false;
    return true;
}

普通版本 对从2到sqrt（n）取模，不为0则是素数, O(logN)

bool judge(ll n)
{
    if(n==2||n==3) return true;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return false;
    return true;
}

高配版本 先对2取模，然后开始对3到sqrt（n）的奇数取模 ,O(0.5*logN)

bool judge(ll n)
{
    if(n==2||n==3) return true;
        if(n%2==0) return false;
    for(int i=3;i<=sqrt(n);i+=2)
        if(n%i==0) return false;
    return true;
}

至尊版本 因为素数只在6的倍数的左右两边，所以先对6取模，看是不是1和5，然后在对5+i6,到sqrt(n)取模， O(0.167logN)只能到1e17左右好像，多次的话就可能会超

bool judge(ll n)
{
    if(n==2||n==3) return true;
    if(n%6!=1&n%6!=5) return false;
    double x=(double)sqrt(n);
    for(int i=5;i<=x;i+=6)
    if(n%i==0||n%(i+2)==0) return false ;
    return true;
}

无敌版本 （判断到1e18都可以） miller_rabbin

ll modular_multi(ll x,ll y,ll mo)
{
    ll t;
    x%=mo;
    for(t=0;y;x=(x<<1)%mo,y>>=1)
        if (y&1)
            t=(t+x)%mo;
    return t;
}
 
ll modular_exp(ll num,ll t,ll mo)
{
    ll ret=1,temp=num%mo;
    for(;t;t>>=1,temp=modular_multi(temp,temp,mo))
        if (t&1)
            ret=modular_multi(ret,temp,mo);
    return ret;
}
 
bool miller_rabbin(ll n)
{
    if (n==2)return true;
    if (n<2||!(n&1))return false;
    int t=0;
    ll a,x,y,u=n-1;
    while((u&1)==0) t++,u>>=1;
    for(int i=0;i<10;i++)
    {
        a=rand()%(n-1)+1;
        x=modular_exp(a,u,n);
        for(int j=0;j<t;j++)
        {
            y=modular_multi(x,x,n);
            if (y==1&&x!=1&&x!=n-1)
                return false;
            ///其中用到定理，如果对模n存在1的非平凡平方根，则n是合数。
            ///如果一个数x满足方程x^2≡1 (mod n),但x不等于对模n来说1的两个‘平凡’平方根：1或-1，则x是对模n来说1的非平凡平方根
            x=y;
        }
        if (x!=1)///根据费马小定理,若n是素数，有a^(n-1)≡1(mod n).因此n不可能是素数
            return false;
    }
    return true;
}