patterncppMinor

Greatest prime number smaller than N where N can be as large as 10^18

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

cannumbergreatestthanwherelargesmallerprime

Problem

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 
#include 

#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 >= 0; i--) if (((a >> i) & 1) == 1) break;
    for (; i >= 0; i--)
    {
        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 >= 1; s++; }
    int i, j;
    for (i = 0; i > t;

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

}

Solution

-
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 `

.  It is shorter, and it should be guaranteed to hold 64 bits on any system.

- 
This is quite a bit of whitespace:

if (n < c1) {

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

            l = 9;
    }


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

if (n < c1) {
    l = 3;
}
else if (n < 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.

Code Snippets

#define c2 341550071728321
#define c1 4759123141

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

typedef unsigned long long ull;

if (n < c1) {

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

            l = 9;
    }

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

Context

StackExchange Code Review Q#25941, answer score: 5

Revisions (0)

No revisions yet.