Greatest prime number smaller than N where N can be as large as 10^18 This is code for finding largest prime number smaller than \$N\$, where \$N\$ can be as large as \$10^{18}\$.  But, it takes 1 minute for \$10^{18}\$. I need to pass it in 2-3 sec.

What changes should I make to pass it?  My compiler used is g++ 4.3.2

The program here runs for multiple test cases.

#include &lt;iostream&gt;
#include &lt;cmath&gt;

#define c2 341550071728321
#define c1 4759123141

using namespace std;

unsigned long long int mul(unsigned long long int a, unsigned long long int b, unsigned      long long int mod)
{
    int i;
    unsigned long long int now = 0;
    for (i = 63; i &gt;= 0; i--) if (((a &gt;&gt; i) &amp; 1) == 1) break;
    for (; i &gt;= 0; i--)
    {
        now &lt;&lt;= 1;
        while (now &gt; mod) now -= mod;
        if (((a &gt;&gt; i) &amp; 1) == 1) now += b;
        while (now &gt; mod) now -= mod;
    }
    return now;
}

unsigned long long int pow(unsigned long long int a, unsigned long long int p, unsigned long long int mod)
{
    if (p == 0) return 1;
    if (p % 2 == 0) return pow(mul(a, a, mod), p / 2, mod);
    return mul(pow(a, p - 1, mod), a, mod);
}


bool MillerRabin(unsigned long long int n)
{
    int l;
     unsigned long long int ar[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23};
    if (n &lt; c1) {

            l = 3;
    }
    else if (n &lt; c2) {
            l = 7;
    }
    else {

            l = 9;
    }
    //l = 9;
    unsigned long long d = n - 1;
    int s = 0;
    while ((d &amp; 1) == 0) { d &gt;&gt;= 1; s++; }
    int i, j;
    for (i = 0; i &lt; l; i++)
    {
        unsigned long long int a  = min(n - 2, ar[i]);
        unsigned long long int now = pow(a, d, n);
        if (now == 1) continue;
        if (now == n - 1) continue;
        for (j = 1; j &lt; s; j++)
        {
            now = mul(now, now, n);
            if (now == n - 1) break;
        }
        if (j == s) return false;
    }
    return true;
}

bool check_prime(unsigned long long int n) {

if(!MillerRabin(n)) return false;
return true;
if(n == 2) return true;
if(n % 2 == 0) return false;
for(unsigned long long int i = 3; i &lt;= sqrt(n); i+=2) {
    if(n % i == 0) return false;
}
return true;
}

int main()
{
int t;

cin &gt;&gt; t;

while(t--) {
    unsigned long long int n;
    cin &gt;&gt; n;
    while(1) {
        if(check_prime(n)) {
            cout &lt;&lt; n &lt;&lt; endl;
            break;
        }
        else {
            n--;
        }
    }
}

}
These macros are not needed in C++:


#define c2 341550071728321
#define c1 4759123141



They should be constants, using the const keyword (or constexpr in C++11):

const int c2 = 341550071728321;
const int c1 = 4759123141;


I've only kept the names the same here because I have no idea what they mean.  Try to avoid using single-char variable names, unless their meaning is already obvious.
You use unsigned long long in many places, which could look verbose.  You could use a typedef so that you can use another (shorter) name in place of them:

typedef unsigned long long ull;


Better yet, you can use std::uint64_t from &lt;cstdint&gt;.  It is shorter, and it should be guaranteed to hold 64 bits on any system.
This is quite a bit of whitespace:


if (n &lt; c1) {

            l = 3;
    }
    else if (n &lt; c2) {
            l = 7;
    }
    else {

            l = 9;
    }



You already use four spaces for indentation, so it should be consistent:

if (n &lt; c1) {
    l = 3;
}
else if (n &lt; c2) {
    l = 7;
}
else {
    l = 9;
}


You're also lacking indentation within main() and check_prime(), but it's okay in your other functions.  I don't see the reason for all this inconsistency if you're not in a hurry to write the code itself.  Make it clean now so that fine-tuning will be easier, both for you and for others.