C Program to Find GCD and LCM of Two Integers

GCD (Greatest Common Divisor)

GCD stands for Greatest Common Divisor. GCD of two numbers is the largest positive integer that completely divides both the given numbers.

Example: GCD(10,15) = 15, GCD(12,15) = 3.

LCM (Least Common Multiple)

LCM stands for Least Common Multiple. It is a method to find the lowest common multiple between the two numbers. LCM of two numbers is the lowest possible number that is divisible by both numbers.

Examples: LCM(10,15) = 30, LCM(12,15) = 60.

Write a C Program to Find the GCD and LCM of two numbers.

1. Take two numbers as input.
2. Find the greater of the two numbers.
3. Keep on dividing the greater number by the smaller number until remainder becomes 0.
4. When the remainder becomes 0 store the smaller number as the GCD of two numbers.
5. If the maximum is completely divisible by both the numbers, store the maximum number as LCM.
6. Else keep on increasing the maximum by one until it is completely divisible by both the numbers.
7. Finally store the new value of maximum as LCM.
5. Exit.

There are several ways to find the GCD and LCM of two numbers in C language. Let’s look at the two different techniques to write a C program to calculate the GCD and LCM of two numbers.

• GCD and LCM of Two Numbers in C using While Loop and LCM Formula
• GCD and LCM of Two Numbers in C using Euclidean Algorithm

In this approach, we find the GCD of two numbers using a while-loop and LCM of two numbers using the formula LCM=num1*num2/GCD.

Here is the source code of the C program to find the GCD and LCM of two numbers using while loop and LCM formula. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the GCD and LCM of two integers 
 * using while loop and Euclids' algorithm
 */
#include <stdio.h>
 
void main()
{
    int num1, num2, gcd, lcm, remainder, numerator, denominator;
 
    printf("Enter two numbers:\n");
    scanf("%d %d", &num1, &num2);
 
    //To find numerator and denominator
    numerator = (num1>num2)?num1:num2;
    denominator = (num1<num2)?num1:num2;
    remainder = numerator % denominator;
 
    while (remainder != 0)
    {
        numerator   = denominator;
        denominator = remainder;
        remainder   = numerator % denominator;
    }
    gcd = denominator;
    lcm = num1 * num2 / gcd;
    printf("GCD of %d and %d = %d\n", num1, num2, gcd);
    printf("LCM of %d and %d = %d\n", num1, num2, lcm);
}

1. In this C program, we are reading the two integer numbers.
2. Compare the two numbers, store the greater number in the numerator and the smaller number in the denominator.
3. Run the while loop until the remainder becomes ‘0’.
4. Inside the while loop keep on dividing the numerator by denominator and store the value in the remainder variable.
5. When the value of the remainder variable becomes ‘0’ come out of the loop and store the value of the denominator in the gcd variable.
6. Now, calculate the lcm by the formula lcm = (num1 * num2) / gcd
7. Print the value of gcd and lcm.

Example:

• Consider, the two numbers 12 and 15, first find the greater of the two numbers and store the greater in the numerator and smaller in the denominator i.e., numerator=15 and denominator=12.
• Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 15%12 = 3.
• Now, enter the while loop and check if the remainder value is ‘0’ or not.
• Now, assign the value of the denominator to the numerator and the value of the remainder to the denominator i.e., numerator=12 and denominator=3
• Calculate the remainder of the two variables i.e., remainder=12%3=0.
• Now, check the while loop condition again, this time remainder = 0, therefore come out of the loop and store the value of the denominator in gcd i.e., gcd = 3.
• Now, using the formula of lcm (lcm = (num1 * num2) / gcd) calculate lcm i.e., lcm = (12*15)/3 = (180/3) = 60.
• Now, print the gcd and lcm of the two numbers.

Time Complexity: O(log(min(a,b)))
The above program for finding GCD and LCM of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the numerator is divided by the denominator.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate gcd and lcm in this case are 12 and 15.

Enter two numbers:
12 15
GCD of 12 and 15 = 3
LCM of 12 and 15 = 60

Testcase 2: The numbers entered by the user to calculate gcd and lcm are 10 and 15.

Enter two numbers:
10 15
GCD of 10 and 15 = 5
LCM of 10 and 15 = 30

In this approach, we find the GCD and LCM of two numbers using Euclidean Algorithm.

Here is the source code of the C program to find the GCD and LCM of two numbers using Euclidean algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the GCD and LCM of Two Numbers using Euclidean Algorithm
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int gcd(int x, int y)
{
    int r = 0, a, b;
    a = (x > y) ? x : y; // a is greater number
    b = (x < y) ? x : y; // b is smaller number
 
    r = b;
    while (a % b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}
 
int lcm(int x, int y)
{
    int a;
    a = (x > y) ? x : y; // a is greater number
    while (1)
    {
        if (a % x == 0 && a % y == 0)
            return a;
        ++a;
    }
}
 
int main()
{
    printf("Enter the two numbers: \n");
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    printf("The GCD of two numbers is: %d", gcd(x, y));
    printf("\nThe LCM of two numbers is: %d", lcm(x, y));
    return 0;
}

1. In this C Program, we are reading the two integer numbers using ‘x’ and ‘y’.
2. The gcd() function is used to find the GCD of two entered integers and the lcm() function is used to find the LCM of two entered integers.
3. The gcd() function is same as the 1st program, the only difference is that we are implementing it using function.
4. For calculating the LCM call the function lcm(). In the lcm() function we are comparing the two numbers x and y and storing the greater number in variable a.
5. Run the while loop until a is divisible by both the numbers x and y.
6. If a is divisible by both the numbers return the value of a as LCM of the two numbers else, increment the value of a by 1 until it gets divisible by both x and y.

Example:

• Consider, the two numbers 12 and 15, first pass the two numbers to gcd() function, find the greater of the two numbers and store the greater in the variable a and smaller in the variable b i.e., a=15 and b=12.
• In the while loop check if a%b is not equal to 0. Since, 15%12 = 3 which is not equal to 0, enter the while loop. Store the value of a%b in the variable r i.e., r=3.
• Assign the value of b in a and r in b i.e., a=12 and b=3.
• Now, again check the while loop, since 12%3=0 come out of the loop and return the value of r i.e., 3. In the main function print the value returned by r as GCD. Therefore, gcd of 15 and 12 is 3.
• Now, pass the values 12 and 15 to lcm() function. Store, the greater number in variable a i.e., a=15. Run the while loop until a is divisible by both x and y. 15%12 = 3, which is bot equal to 0, so increment the value of a by 1 and again check the condition in the while loop.
• Repeat this process until a is divisible by both x and y. By repeating this process, we get value of a as 60.
• Check if it is divisible by both x and y. The condition is true therefore return the value of a to the main function and print it as LCM of the two numbers.

Time Complexity: O(n)
The above program for finding GCD and LCM of two numbers has a time complexity of O(n), as the while loop in LCM function runs for n number of times.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate gcd and lcm in this case are 12 and 15.

Enter two numbers:
12 15
GCD of 12 and 15 = 3
LCM of 12 and 15 = 60

Testcase 2: The numbers entered by the user to calculate gcd and lcm are 50 and 20.

Enter the two numbers:
50 20
The GCD of two numbers is: 10
The LCM of two numbers is: 100

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.