Find the largest sum of the GCD and LCM of two numbers in a range 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 &lt;iostream&gt;

using namespace std;

int main()
{
    int n;

    cin &gt;&gt; n;

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

    for(int i = 1; i &lt;= n; i++)
    {
        for(int j = 1; j &lt;= n; j++)
        {
            if(i &gt; j){smaller=j;}
            else{smaller=i;}

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

    return 0;
}
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 &gt; 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 &lt;= n; i++) {
    // smaller = j
    for(int j = 1; j &lt; i; j++) {
        for(int y = 1; y &lt;= j/*smaller*/; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i; j &lt;= n; j++) {
        for(int y = 1; y &lt;= i/*smaller*/; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; 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 &gt; highest_value) highest_value = equation;


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

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


we now have

for(int i = 1; i &lt;= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation &gt; highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j &lt; i; j++) {
        for(int y = 1; y &lt;= j/*smaller*/; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i+1; j &lt;= n; j++) {
        for(int y = 1; y &lt;= i/*smaller*/; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; 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 &lt;= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation &gt; highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j &lt; i; j++) {
        for(int y = 1; y &lt;= j/*smaller*/; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; 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 &lt;= n; i++) {
    // smaller = j
    for(int j = 1; j &lt; i; j++) {
        for(int y = 1; y &lt;= j; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation &gt; highest_value) highest_value = equation;
    }
}

return highest_value;


Now let's look at the inner-most loop

for(int y = 1; y &lt;= j; y++) {
    if(i%y==0 &amp;&amp; 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 &gt; highest_value) highest_value = equation;

for(int y = 2; y &lt;= j; y++) {
    if(i%y==0 &amp;&amp; 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 &gt; 0 ) {
    equation = 1 + n*(n-1);
    if(equation &gt; highest_value) highest_value = equation;
}


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

int highest_value, gcd, equation;

if ( n &gt; 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 &gt; 2 ) {
    highest_value = 1 + n*(n-1);
} else {
    highest_value = 2 * n;
}

for(int i = 3; i &lt;= n; i++) {
    for(int j = 2; j &lt; i; j++) {
        for(int y = 2; y &lt;= j; y++) {
            if(i%y==0 &amp;&amp; j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd);
        if(equation &gt; 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 &gt; 2) ? ( 1+n*(n-1) ) : ( 2*n );