**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”.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check C Books
- Watch Advanced C Programming Videos
- Check Computer Science Books
- Apply for Computer Science Internship
- Practice BCA MCQs