bool primeCheck(long long p)
{
    const long long k=100;
    vector<long long> x;
    long long s=0,n=p-1;
    while(!(n&1))
    {
        ++s;
        n>>=1;
    }
    if(!s)
        return false;
    for(long long a=2;a<k+1;++a)
    {
        x.push_back(powMod(a,n,p));
        for(int i=1;i<=s-1;++i)
            x.push_back(powMod(x[i-1],2,p));
        bool l=(x[0]-1)?false:true;
        for(int i=0;i<x.size();++i)
        {
            if(x[i]==p-1)
                l=true;
        }
        x.clear();
        if(!l)
            return l;
    }
    return true;
}