素数判定(高速)
(give_us_tmp/is_prime.cpp)

/**
 * @brief 素数判定(高速)
 * 
 * verified with    :https://judge.yosupo.jp/problem/factorize
 * submission       :https://judge.yosupo.jp/submission/28308
 */
bool is_prime(ll n){
    if(n<=1)return 0;
    if(n==2)return 1;
    if(n%2==0)return 0;
    ll s=0,d=n-1;
    while(d%2)d/=2,s++;
    auto mod_pow=[](__int128_t a,__int128_t b,__int128_t n){
        ll res=1;
        while(b){
            if(b%2)res=res*a%n;
            a=a*a%n;
            b/=2;
        }
        return (ll)(res);
    };
    for(ll e:{2,3,5,7,11,13,17,19,23,29,31,37}){
        if(n<=e)break;
        if(mod_pow(e,d,n)==1)continue;
        bool b=1;
        for(int i=0;i<s;i++){
            if(mod_pow(e,d<<i,n)==n-1)b=0;
        }
        if(b)return 0;
    }
    return 1;
}

#line 1 "give_us_tmp/is_prime.cpp"
/**
 * @brief 素数判定(高速)
 * 
 * verified with    :https://judge.yosupo.jp/problem/factorize
 * submission       :https://judge.yosupo.jp/submission/28308
 */
bool is_prime(ll n){
    if(n<=1)return 0;
    if(n==2)return 1;
    if(n%2==0)return 0;
    ll s=0,d=n-1;
    while(d%2)d/=2,s++;
    auto mod_pow=[](__int128_t a,__int128_t b,__int128_t n){
        ll res=1;
        while(b){
            if(b%2)res=res*a%n;
            a=a*a%n;
            b/=2;
        }
        return (ll)(res);
    };
    for(ll e:{2,3,5,7,11,13,17,19,23,29,31,37}){
        if(n<=e)break;
        if(mod_pow(e,d,n)==1)continue;
        bool b=1;
        for(int i=0;i<s;i++){
            if(mod_pow(e,d<<i,n)==n-1)b=0;
        }
        if(b)return 0;
    }
    return 1;
}