判断一个数是不是质数

    1. long long multiMod(long long a,long long b,long long mod)
    2. {
    3.     long long res=0;
    4.     while(b)
    5.     {
    6.         if(b&1)
    7.         {
    8.             res=res+a;
    9.             if(res>=mod) res-=mod;
    10.         }
    11.         a=a+a;
    12.         if(a>=mod) a-=mod;
    13.         b>>=1;
    14.     }
    15.     return res;
    16. }
    17. long long powMod(long long a,long long b,long long mod)
    18. {
    19.     long long res=1;
    20.     while(b)
    21.     {
    22.         if(b&1)
    23.         {
    24.             res=multiMod(res,a,mod);
    25.         }
    26.         a=multiMod(a,a,mod);
    27.         b>>=1;
    28.     }
    29.     return res;
    30. }
    31. bool check(long long a,long long n,long long x,int t)
    32. {
    33.     long long res=powMod(a,x,n);
    34.     long long last=res;
    35.     for(int i=1; i<=t; i++)
    36.     {
    37.         res=multiMod(res,res,n);
    38.         if(res==1&&last!=1&&last!=n-1) return true;
    39.         last=res;
    40.     }
    41.     return res!=1;
    42. }
    43. long long randomVal(long long n)
    44. {
    45.     return ((double)rand()/RAND_MAX*n+0.5);
    46. }
    47. const int times=8;
    48. bool IsPrime(long long n)
    49. {
    50.     if(n<2) return false;
    51.     if(n==2) return true;
    52.     if(!(n&1)) return false;
    53.     long long x=n-1,t=0;
    54.     while((x&1)==0)
    55.     {
    56.         t++;
    57.         x>>=1;
    58.     }
    59.     for(int i=0; i<times; i++)
    60.     {
    61.         long long a=randomVal(n-2)+1;
    62.         if(check(a,n,x,t)) return false;
    63.     }
    64.     return true;
    65. }