miller_rabin_test.sublime-snippet

<snippet>
	<content><![CDATA[

ll power(ll n , ll p , ll MOD){
  ll ans = 1;
  n %= MOD;
  for(;p;p>>=1){
    if(p&1){
      ans = (ans*n)%MOD;
    }
    n = (n*n)%MOD;
  }
  return ans;
}
bool miillerTest(ll d, ll n) { 
  ll a = 2 + rand() % (n - 4); 
  ll x = power(a, d, n); 
  if (x == 1  || x == n-1) 
     return true;  
  while (d != n-1) { 
    x = (x * x) % n; 
    d *= 2; 
    if (x == 1)      return false; 
    if (x == n-1)    return true; 
  } 
  return false; 
} 

bool isPrime(ll n, ll k) {  
  if (n <= 1 || n == 4)  return false; 
  if (n <= 3) return true; 
  ll d = n - 1; 
  while (d % 2 == 0) 
      d /= 2; 
  for (ll i = 0; i < k; i++) 
   if (miillerTest(d, n) == false) 
    return false; 
  return true; 
} 

]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>millerrabintest</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<scope>source.cpp , source.cc , source.c , source.c++</scope>
</snippet>