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.2The program here runs for multiple test cases.#include <iostream>#include <cmath>#define c2 341550071728321#define c1 4759123141using 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 >= 0; i--) if (((a >> i) & 1) == 1) break;    for (; i >= 0; i--)    {        now <<= 1;        while (now > mod) now -= mod;        if (((a >> i) & 1) == 1) now += b;        while (now > 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 < c1) {            l = 3;    }    else if (n < c2) {            l = 7;    }    else {            l = 9;    }    //l = 9;    unsigned long long d = n - 1;    int s = 0;    while ((d & 1) == 0) { d >>= 1; s++; }    int i, j;    for (i = 0; i < 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 < 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 <= sqrt(n); i+=2) {    if(n % i == 0) return false;}return true;}int main(){int t;cin >> t;while(t--) {    unsigned long long int n;    cin >> n;    while(1) {        if(check_prime(n)) {            cout << n << endl;            break;        }        else {            n--;        }    }}}
Greatest prime number smaller than N where N can be as large as 10^18
c++;performance;primes