Largest LCM of partitions of a number

Question

Suppose there is a number N which can be divided into two positive non zero numbers X and Y i.e N = X + Y. There will be N/2 pairs of (X,Y).

I want to find the largest LCM(Least common multiple) of X & Y

Example
5 = (1 + 4) and 5 = (2 + 3)
Since LCM(1,4) = 4 < LCM(2,3) = 6 the largest LCM will be LCM(2,3) = 6.

CODE

#include <stdio.h>
int lcm(int, int);
int main(void) 
{
 int counter = 0;
 int lowerBound = 0, upperBound, input, result; // input is the n
 printf("input = ");
 scanf("%d",&input);
 int max = -1;
 upperBound = input; // at first upperBound will be the input
 for(counter=0; counter < input/2; counter++) // we will iterate till the input/2 terms 
 {
 lowerBound++;
 upperBound--;
 // in every iteration we will compute the lcm of lowerBound and upperBound
 // so 1st iteration : compute lcm(1, n-1)
 // 2nd iteration : compute lcm(2, n-2)
 // 3rd iteration : compute lcm(3, n-3)
 // .......after ((n/2)-1)th iteration.....
 // if n is even : compute lcm(n/2, n/2)
 // if n is odd : compute lcm((n/2)-1, n/2)
 result = lcm(lowerBound,upperBound); // store the result
 if(result >= max) // if result is maximum update the maximum
 {
 max = result;
 }
 }
 printf("output = %d",max);
 return 0;
}
int lcm(int x, int y)
{
 int n1 = x, n2 = y;
 while(n1 != n2)
 {
 if(n1 > n2)
 n1 = n1 - n2;
 else
 n2 = n2 - n1;
 }
 return((x*y) / n1);
}

OUTPUT 1

input = 10
output = 21

OUTPUT 2

input = 11
output = 30

---

UPDATE 1

After Aseem Bansal's answer I try to find a more optimize way to solve the problem and i came up with this code

#include<stdio.h>
int main(void)
{
 int input, result = 0;
 printf("Enter the input = ");
 scanf("%d",&input);
 while(input <= 0) // if input is negative ask again
 {
 printf("Enter a positive non zero number :");
 scanf("%d",&input);
 }
 int middle = (input/2);
 if(input%2 != 0) // if the input is an odd number
 {
 result = (middle * (middle+1)); 
 }
 else // if input is an even number
 {
 result = middle%2 == 0 ? ((middle-1) * (middle+1))
 : ((middle-2) * (middle+2));
 }
 printf("result = %d",result);
 return 0;
}

OUTPUT 1

Enter the input = 13
result = 42

OUTPUT 2

Enter the input = 12
result = 35

OUTPUT 3

Enter the input = 10
result = 21

EXPLANATION

As for any odd number the middle and middle+1 are highest coprime numbers, so the GCD will be 1. Therefore LCM will be product of middle and middle+1.

But for any even number the LCM of middle and middle+1 is 1. So we need to find the nearest coprime numbers. If middle is even then the nearest coprime numbers are middle-1 and middle+1 otherwise the nearest coprime numbers are middle-2 and middle+2. The product will be the result.

NOTE

here middle is floor of (middle).

Can it be more optimized? Any review is welcome.

• William Morris: Please add a definition of LCM (LCM: the least common multiple of two numbers is the smallest number (not zero) that is a multiple of both).
• Aseem Bansal: Related question on CS.
• Anirban Nag 'tintinmj': @AseemBansal yes actually if you look closely one of the answer is given by me.
• Aseem Bansal: I noticed that. Just wanted others reading this question to know that.
• Aseem Bansal: @tintinmj I rejected your edit because your current code calculates 3 LCMs while my answer explains how it can be done by calculating only one of them. You might need to read my answer's EDIT3 again.

Answer 1

I am not sure about the overall algorithm but there are better ways for finding LCM. You should use a different algorithm. Try Euclid's algorithm to find the GCD.

Then calculate result(your LCM) in main() as

result = (lowerbound * upperbound)/gcd(lowerbound upperbound);

The problem with your LCM function is that subtraction isn't the best way for finding the GCD which you are currently doing. It will take too long. Just consider the case of x = 1 and y = 100000. It should be easy to see that number of subtractions is much higher in this case and the program would be very slow.

---

If you don't want to change the algorithm(which you should) then the least optimization that I can think is to not declare n1 and n2 separately in the function lcm. Just use x and y. Do the final division by the product in the main function. It will at least save you 2 variables.

---

EDIT

I came up with a much better optimization. In your main loop instead of going from the outside pairs i.e (1, n-1) to the inside pairs you would do much better by going from the inside.

Example

5 = (1,4) and 5 = (2,3). The maximum is found at 5 = (2,3).

7 = (1,6) , 7 = (2,5) and 7 = (3,4). The maximum is at 7 = (3,4).

The answer is in the middle. You'll get it without a loop.

But there is a big problem. This reasoning works only for odd numbers. I tried writing down numbers on paper and solved it by hand. I'll need some more time to find out a pattern for even numbers.

But for odd numbers this is probably the best optimization.

EDIT2

In the main function instead of if(result >= max) you should be using if(result > max). What is the use of replacing the number with the same number? One less operation.

You don't need to initialize counter at the beginning. You are doing that in the for loop.

EDIT3:

For the case of even numbers the maximum lcm will be either lcm((input/2)-2, (input/2)+2) or lcm((input/2)-1, (input/2)+1). It's easy to find which will be maximum without calculating both of them.

If input/2 is even then lcm((input/2)-1, (input/2)+1) should be maximum otheriwse it should be lcm((input/2)-2, (input/2)+2).

---

EDIT After OP's Update 1

How about this as a better code

#include<stdio.h>
int main(void)
{
 int input, result;
 printf("Enter the input = ");
 scanf("%d",&input);
 while (input <= 0)
 {
 printf("Enter a positive non zero number :");
 scanf("%d",&input);
 }
 // (x % 2) used as a condition in C means checking x for odd number
 int middle = input/2;
 result = input % 2 ? (middle % 2 ? middle * middle - 4 : middle * middle - 1)
 : middle * (middle + 1);
 printf("Result = %d",result);
 return 0;
}

Removed unnecessary braces, spaces, comparisons and comments. Comments are needed but commenting obvious things is just noise. I prefer single space on both sides of operators.

• Anirban Nag 'tintinmj': i also thought about nested ternary operators, this minimizes the code but create readability issue. I like the (middle * middle) - 4 it's for (a+b) * (a-b) but seeing this code only once someone will stumble, just a thought.
• Aseem Bansal: Seeing (a + b) * (a - b) will also lead people to think why if they don't know the logic behind it. So that should not be an issue. If you can explain that then you can also explain this.
• Aseem Bansal: If if-else is nested a lot to just decide the value of a variable that would create more readability issues. This makes things clear IMHO.