Least Common Multiple in C

Problem

Write a program to find the least common multiple of two numbers using loops.

Example:

Input:
Enter the two numbers: 5 7

Output:
35

Expectations:

You need to write the complete program using the following template as the starter:

#include <stdio.h>

int main() {
    int a, b;
    
    printf("Enter the two numbers: ");
    scanf("%d%d", &a, &b);

    // Write your code here 
    
    return 0;
}

Copy and paste the above code in your favorite IDE and start writing your code after the comment “// Write your code here.”

Sample Test Cases:

To verify the program you have written, go ahead and test your program using the following test cases:

Don’t forget to try the code on your own before diving into the solution.

Solution

We are going to use GCD (Greatest Common Divisor) to find the LCM of two numbers. We can use the following formula to calculate the LCM:

LCM(a, b) * GCD(a, b) = a * b

It’s a famous formula which states that the product of LCM and GCD of numbers a and b is equivalent to the product of two numbers. 

So, in order to calculate LCM, we first need to calculate GCD of two numbers. The GCD or HCF (Highest Common Factor) of two numbers a and b can be obtained using the following formula:

GCD(a, b) = GCD(b, a%b)

The following figure demonstrates how the GCD works:

The function to calculate GCD of two numbers look like the following:

int gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

And the function to calculate the LCM of two numbers is as follows:

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

The complete program is as follows:

#include <stdio.h>

int gcd(int a, int b) {
    int temp;
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main()
{
    int a, b;
    
    printf("Enter the two numbers: ");
    scanf("%d%d", &a, &b);
    
    printf("%d", lcm(a, b));

    return 0;
}

Input: 
12 15

Output:
60

Check the program for all test cases and you will find that the program is working as expected.