Miller Rabin Primality Test

/// Way : 2

#include<bits/stdc++.h>

#define ll unsigned long long int

using namespace std;

ll base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37};

ll mod(ll a, ll b, ll m)

{

    ll r = 0;

    a = a%m;

    while(b > 0)

    {

        if(b&1)

            r = (r + a)%m;

        b = (b >> 1); /*** b = b/2 ***/

        a = (a + a)%m;

    }

    return r;

}

ll power(ll a, ll d, ll n)

{

    ll r = 1;

    a = a%n;

    while(d > 0)

    {

        if(d&1) /*** d%2 == 1 ***/

            r = mod(r, a, n);

        d = (d >> 1); /*** d = d/2 ***/

        a = mod(a, a, n);

    }

    return r;

}

bool miller_rabin(ll n)

{

    ll d = n-1;

    for(int i=0;i<12;i++)

    {

        if(base[i] == n)

            return true;

        if(power(base[i], d, n) != 1)

            return false;

    }

    return true;

}

int main()

{

    ll n;

    cout << "Enter Any Number :: ";

    cin >> n;

    if(n <= 1 || (n%2 == 0 && n != 2))

        cout << n << " :: Not Prime." << "\n";

    else if(n <= 3)

        cout << n << " :: Prime." << "\n";

    else

    {

        if(miller_rabin(n))

            cout << n << " :: Prime." << "\n";

        else

            cout << n << " :: Not Prime." << "\n";

    }

    return 0;

}