#include <iostream>

#include <random>

#include <time.h>

using namespace std;

typedef unsigned __int64 llong;//无符号64位整形

//typedef为已有的类型起一个别名。

//既然是别名，对同一类型可以起多个别名。这在C/C++中是允许的，各个别名和真名的作用都是一样有效的。

llong mod_pro(llong x,llong y,llong n)

{

    llong ret=0,tmp=x%n;

    while(y)

    {

        if(y&0x1)

            if((ret+=tmp)>n)

                ret-=n;

        if((tmp<<=1)>n)

            tmp-=n;

        y>>=1;//>>= 意思为：右移后赋值(按位移)

    }

    return ret;

}

//a^b mod c

llong mod(llong a,llong b,llong c)//a：原理中的b，b：m,c:n

{

    llong ret=1;

    while(b)

    {

        if(b&0x1)//b不为偶数

            ret=mod_pro(ret,a,c);//1,随机数，n

        a=mod_pro(a,a,c);

        b>>=1;

    }

    return ret;

}

llong ran()

{

    llong ret =rand();

    return ret*rand();

}

bool is_prime(llong n,int t)//轮数为3

{

    if(n<2)

        return false;

    if(n==2)

        return true;

    if(!(n&0x1))//按位与运算(为偶数)

        return false;

    llong k=0,m,a,i;

    for(m=n-1; !(m&1); m>>=1,k++);// !(m&1):m是偶数

    cout<<m<<" "<<k<<endl;//m是m，k是s：n-1= 2^s*m

    while(t--)

    {

        a=mod(ran()%(n-2)+2,m,n);//ran()%(n-2)+2：随机整数b

        if(a!=1)//圈3

        {

            for(i=0; i<k&&a!=n-1; i++)

            {

                a=mod_pro(a,a,n);

            }

            if(i>=k)

                return false;

        }

    }

    return true;

}

int main()

{

    llong n;

    cout<<"请输入一个大于三的整数：";

    while(scanf("%I64u",&n)!=EOF)//__int64结构的输入格式

    {

        clockid_t starttime,endtime;

        starttime=clock();

        if(is_prime(n,3))

            cout<<"YES\n";

        else

            cout<<"NO\n";

        endtime=clock();

        cout<<"用时"<<endtime-starttime<<"毫秒\n"<<endl;

        cout<<"请输入一个大于三的整数：";

    }

    return 0;

}