2
\$\begingroup\$

The program is supposed to get one number n as input, and output the max value of gcd + lcm of two numbers that range from 1 to n.

For example, if n == 3, the answer is 7 because gcd(3,2) == 1 and lcm(3,2) == 6.

The issue is that the code works really slowly and the double loop makes it so numbers above basically 1000 take forever to run. How do I make it run faster?

#include <iostream>

using namespace std;

int main()
{
    int n;

    cin >> n;

    int highest_value = 0,equation;
    int gcd,smaller;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i > j){smaller=j;}
            else{smaller=i;}

            for(int y = 1; y <= smaller; y++)
            {
                if(i%y==0 && j%y==0) gcd = y;
            }
            equation = gcd+((i*j)/gcd);
                if(equation > highest_value) highest_value = equation;
        }
    }
    cout << highest_value;

    return 0;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to CR! This was migrated from SO, but please take the tour and see How to Ask. It'd be helpful if you'd use the explanation you used on SO, namely, that the code isn't performant enough. Otherwise, this just feels like a code dump. Thanks for clarifying and explaining. \$\endgroup\$ – ggorlen Sep 25 at 19:12
4
\$\begingroup\$

I decided to take a stab at this, and I ended up reducing your algorithm down to one line (tested for equality with the original algorithm from n = [0,500] :

highest_value = (n > 2) ? ( 1+n*(n-1) ) : ( 2*n );

If you would like to see the steps I took, then please see my steps below...

Let's start by removing the comparison in the 2nd loop by splitting up the 2nd loop into 2 parts:

for(int i = 1; i <= n; i++) {
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i; j <= n; j++) {
        for(int y = 1; y <= i/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

Now let's extract the simple case where i == j by adding

// i == j
// gcd = i;
// equation = gcd+((i*j)/gcd);
// equation = i + (i*i)/i
equation = 2 * i;
if(equation > highest_value) highest_value = equation;

and changing the limits of the second loop to exclude i == j

for(int j = i+1; j <= n; j++) {

we now have

for(int i = 1; i <= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation > highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i+1; j <= n; j++) {
        for(int y = 1; y <= i/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

we can observe that the second loop checks the same values (just mirrored with i and j), so we can get rid of the second loop entirely giving us:

for(int i = 1; i <= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation > highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

we can also observe that the maximum value for the i == j case will be where i == n, so we can get rid of that section and start our highest_value at 2*n :

int highest_value = 2*n;
int equation, gcd;

for(int i = 1; i <= n; i++) {
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

return highest_value;

Now let's look at the inner-most loop

for(int y = 1; y <= j; y++) {
    if(i%y==0 && j%y==0) gcd = y;
}

we know that y == 1 is a simple case where gcd = 1 and equation = 1 + i*j, so we can extract that from the loop:

equation = 1 + i*j;
if(equation > highest_value) highest_value = equation;

for(int y = 2; y <= j; y++) {
    if(i%y==0 && j%y==0) gcd = y;
}

let's also notice that the equation 1 + i*j has a maximum consistent with the maximum values of i and j where i = n and j = n-1 which gives us 1 + n*(n-1) or 1 + n*n - n. Now we can move this equation to the beginning of the function and check it against our initial highest_value of 2 * n. Don't forget to exclude the case where n == 0, because it is impossible to achieve a value of i or j == 0 inside the loop.

int highest_value = 2*n;
int gcd, equation;

if ( n > 0 ) {
    equation = 1 + n*(n-1);
    if(equation > highest_value) highest_value = equation;
}

We can notice that our new equation exceed our initial equation at a value of n >= 3

int highest_value, gcd, equation;

if ( n > 2 ) {
    highest_value = 1 + n*(n-1);
} else {
    highest_value = 2 * n;
}

We can notice that i == 1 and j == 1 will never be divisible by the initial value of y, so we can start them at 2. Then notice that the j loop never happens if i == 2, so we can start i at 3.

int highest_value, gcd, equation;

if ( n > 2 ) {
    highest_value = 1 + n*(n-1);
} else {
    highest_value = 2 * n;
}

for(int i = 3; i <= n; i++) {
    for(int j = 2; j < i; j++) {
        for(int y = 2; y <= j; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd);
        if(equation > highest_value) highest_value = equation;

    }
}

return highest_value;

Finally... We can notice a pattern where we can take this approach indefinitely where we can continue to factor our i and j, so I noticed a pattern where the initial highest_value is true for every i and j, so the final function is :

highest_value = (n > 2) ? ( 1+n*(n-1) ) : ( 2*n );
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.