Miller-Rabin's Primality Test

/*
** This is a C++ implementation of Miller-Rabin's primality testing.
** If it returns false, then it is composite, and if it returns true,
** then it is LIKELY to be prime.
** Runtime: O(klogn) [k is the accuracy parameter]
*/

#include <cstdio>
#include <cstdlib>

int power(int x, int y, int p)
{
    int res=1;
    x%=p;

    while(y>0)
    {
        if(y&1) res*=x, res%=p;
 
        y=y>>1;
        x*=x, x%=p;
    }

    return res;
}

bool millerRabinTest(int d, int n)
{
    int a=2+rand()%(n-4), x=power(a,d,n);
 
    if(x==1 || x==n-1) return true;
 
    while(d!=n-1)
    {
        x*=x, x%=n;
        d<<=1;
 
        if(x==1) return false;
        if(x==n-1) return true;
    }
 
    return false;
}
 
bool isPrime(int n,int accuracy)
{
    if(n<=1 || n==4)  return false;
    if(n<=3) return true;
 
    int d=n-1;
    while(!(d&1)) d>>=1;
 
    while(accuracy--) if(!millerRabinTest(d,n)) return false;
 
    return true;
}
 
int main()
{
    printf("%d\n", isPrime(37,5));
    return 0;
}