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

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

Write a C Program to Find the GCD 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 print the smaller number i.e., the denominator as the output.

5. Exit.

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

- GCD of Two Numbers in C using While Loop
- GCD of Two Numbers in C using For Loop
- GCD of Two Numbers in C using Recursion
- GCD of Two Numbers in C using Euclidean Algorithm
- GCD of Two Numbers in C using Recursive Euclidean Algorithm

In this approach, we find the GCD of two numbers using a while loop.

Here is the source code of the C program to find the GCD of two numbers using a while-loop. 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 of two integers using While-loop */ #include<stdio.h> void main() { int num1, num2, gcd, remainder, numerator, denominator; printf("Enter two numbers\n"); scanf("%d %d", &num1, &num2); if (num1 > num2) { numerator = num1; denominator = num2; } else { numerator = num2; denominator = num1; } remainder = numerator % denominator; while (remainder != 0) { numerator = denominator; denominator = remainder; remainder = numerator % denominator; } gcd = denominator; printf("GCD of %d and %d = %d\n", num1, num2, gcd); }

1. Take the two numbers **num1** and **num2** as input.

2. Store the greater number in the variable **numerator** and the smaller number in the variable **denominator**.

3. Run the while loop until the **remainder** becomes ‘0’. Inside the while loop keep on dividing the **numerator** by **denominator** and store the value in the **remainder** variable.

4. 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.

5. Print the **gcd**.

**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 **numerator** i.e., **numerator=12** and **denominator=3** then 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, print **gcd** as 3.

**Time Complexity: O(log(min(a,b)))**

The above program for finding GCD 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 in this case are 12 and 15.

Enter the two numbers: 12 15 GCD of 12 and 15 = 3

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

Enter the two numbers: 50 30 GCD of 50 and 30 = 10

In this approach, we find the GCD of two numbers using for-loop.

Here is the source code of the C program to find the GCD of two numbers using for loop. 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 of two integers using for-loop */ #include<stdio.h> void main() { int n1, n2, i, gcd; printf("Enter two integers: "); scanf("%d %d", &n1, &n2); int min = (n1 < n2)? n1:n2; // to find minimum of the two numbers. for(i=min; i >=1; --i) { // Checks if i divides both the integers if(n1%i==0 && n2%i==0) { gcd = i; break; } } printf("G.C.D of %d and %d is %d", n1, n2, gcd); }

1. Take the two integers **n1** and **n2** as input.

2. Store the minimum of the two integers in the variable **min**.

3. Run the for loop from **i=min** to **i>=1** and decrease the value of **i** by 1 after each iteration.

4. Divide both the numbers **n1** and **n2** by **i**, if both gives **remainder = 0** then store the value of **i** in **gcd** variable and break the for loop. (We are breaking the for loop because we are checking for GCD from the greatest number possible for GCD. So, the 1st greatest number that divides both the number completely is the GCD of the two numbers.)

5. Print the **gcd**.

**Example:**

Consider the two numbers are **n1=10** and **n2=15**. Find minimum of the two numbers and store it in the variable **min** i.e., **min=10**. Run the for loop from **i = min** to 1 and check if i divides both **n1** and **n2** completely. At the beginning **i = 1**, 10%10 gives the remainder as 0 but 15 %10 is 5 so, the if condition is false, decrement the value of **i** to 9 and again check the if condition. Repeat this step until if condition becomes true. Check for **i=5**, so 10%5=0 and 15%5=0 so, enter the if condition. Inside if statement assign the value of **i** to variable **gcd**. Now, break the condition i.e., come out of the for loop and print the value of **gcd**. Therefore, **gcd** of 10 and 15 is 5.

**Time Complexity: O(min(n1,n2)))**

The above program for finding GCD of two numbers has a time complexity of O(min(n1,n2)), as the for loop runs for minimum of number of times of n1 and n2.

**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 in this case are 10 and 15.

Enter the two numbers: 10 15 G.C.D of 10 and 15 is 5

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

Enter the two numbers: 15 24 G.C.D of 15 and 24 is 3

In this approach, gcd() function is used to find the GCD of two entered numbers using recursion.

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

/* * C Program to find GCD of given Numbers using Recursion */ #include<stdio.h> int gcd(int, int); int main() { int a, b, result; printf("Enter the two numbers to find their GCD: "); scanf("%d%d", &a, &b); result = gcd(a, b); printf("The GCD of %d and %d is %d.\n", a, b, result); } int gcd(int a, int b) { while (a != b) { if (a > b) { return gcd(a - b, b); } else { return gcd(a, b - a); } } return a; }

In this C Program, we are reading the two integer numbers using ‘**a**’ and ‘**b**’ variable. The **gcd()** function is used to find the GCD of two entered integers using recursion.

While loop is used to check that both the ‘**a**’ and ‘**b**’ variable values are not equal. If the condition is true then execute the loop. Otherwise, return the value of ‘**a**’ variable. If else condition statement is used to check the value of ‘**a**’ variable is greater than the value of ‘**b**’ variable.

If the condition is true, then recursively call the **gcd()** function passing the **values (a-b, b)**. Otherwise, if the condition is false, then recursively call the **gcd()** function passing the values **(a, b-a)**. Run this until while loop condition becomes false and then return the value of ‘**a**’ as output.

**Example:**

Consider, the two numbers **a** and **b** are 15 and 20. Enter the **gcd()** function and check if both are equal or not. Since, 15! = 20 enter the while-loop. Inside the while-loop we see that **a<b**, therefore, enter the else statement and recursively call **gcd** function passing the values (a, b-a) i.e., (15,5).

Again, follow the same procedure as above. This time **a>b**, therefore, execute the if statement and call the function **gcd()** passing the values (a-b, b) i.e., (10,5).

Repeat the same process again. This time **a>b**, therefore, execute the if statement and call the function **gcd()** passing the values (a-b, b) i.e., (5,5).

Now, **a=b**, therefore do not enter the while loop and return the value of ‘**a**‘ i.e., 5 as **gcd**.

**Time Complexity: O(log(min(a,b)))**

The above program for finding GCD of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the lesser number is subtracted from the greater number until both becomes equal.

**Space Complexity: O(log(min(a,b)))**

In the above program, space complexity is O(log(min(a, b))) as the value of a and b gets stored in the memory until the recursive function gets terminated.

**Testcase 1:** In this case, the numbers entered by the user to find gcd using recursion are 15 and 20.

Enter the two numbers to find their GCD: 15 20 The GCD of 15 and 20 is 5.

**Testcase 2:** The numbers entered by the user to find gcd using recursion are 50 and 20.

Enter the two numbers to find their GCD: 50 20 The GCD of 50 and 20 is 10.

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

Here is the source code of the C program to find the GCD 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 GCD of two Numbers using Euclidean Algorithm */ #include<stdio.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 main(int argc, char **argv) { printf("Enter the two numbers: "); int x, y; scanf("%d", &x); scanf("%d", &y); printf("The GCD of two numbers is: %d", gcd(x, y)); return 0; }

In this C Program, we are reading the two integer numbers using ‘**x**’ and ‘**y**’. The **gcd()** function is used to find the GCD of two entered integers without recursion.

This program is same as the “using while” program, the only difference is that we are implementing it using function.

The while loop terminates when **a** modulus **b** becomes 0, and **r** is returned back to the main function.

**Example:**

Consider, the two numbers 12 and 15, first 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.

**Time Complexity: O(log(min(a,b)))**

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

**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:** In this case, the numbers entered by the user to calculate gcd using the Euclidean algorithm are 12 and 15.

Enter the two numbers: 12 15 The GCD of two numbers is: 3

**Testcase 2:** The numbers entered by the user to calculate gcd using the Euclidean algorithm are 50 and 20.

Enter the two numbers: 50 20 The GCD of two numbers: 10

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

Here is the source code of the C program to find the GCD of two numbers using Recursive 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 GCD of two Numbers using Recursive Euclidean Algorithm */ #include<stdio.h> int gcd_algorithm(int a, int b) { int x = (a > b) ? a : b; // a is greater number int y = (a < b) ? a : b; // b is smaller number if (y == 0) { return x; } else { return gcd_algorithm(y, (x % y)); } } int main() { int num1, num2, gcd; printf("\nEnter two numbers to find gcd using Euclidean algorithm: "); scanf("%d%d", &num1, &num2); gcd = gcd_algorithm(num1, num2); printf("The GCD of %d and %d is %d\n", num1, num2, gcd); return 0; }

In this C Program, we are reading the two integer numbers using ‘**num1**’ and ‘**num2**’. The **gcd_algorithm()** function is used to find the GCD of two entered integers using recursive Euclidean Algorithm.

Store the greater of the two numbers in variable **x** and smaller number in variable **y**. If **y** becomes 0 then return **x** else recursively call the **gcd_algorithm()** function with parameters **(y,(x%y))**. Repeat this process until **y** becomes 0.

**Example:**

Consider the two numbers are 20 and 12. The greater number i.e., 20 is stored in **x** and the smaller number i.e., 12 is stored in **y**. Check the condition if **y==0**, since condition is false execute the else statement and recursively call the **gcd_algorithm()** function by passing the values as **(y,(x%y))** i.e., (12,8). Now, repeat the same process. **X=12** and **y=8**. As **y** is not equal to 0 again execute the else part and call the recursive function **gcd_algorithm()** by passing the values as **(y,(x%y))** i.e., (8,4). In the next step again the same process will be followed and the values that will be returned to the function are (4,0).

Now, **x=4** and **y=0**. Check the if condition, this time the condition i.e., **y==0** becomes true and hence **x** i.e., 4 is returned as GCD. In the main function print 4 as GCD.

**Time Complexity: O(log(min(x,y)))**

The above program for finding GCD of two numbers has a time complexity of O(log(min(x,y))), as the gcd_algorithm() function runs for minimum of number of times x is divided by y.

**Space Complexity: O(log(min(x,y)))**

In the above program, space complexity is O(log(min(x, y))) as the value of x and y gets stored in the memory until the recursive function gets terminated.

**Testcase 1:** In this case, the numbers entered by the user to calculate gcd using the Euclidean algorithm are 12 and 20.

Enter two numbers to find gcd using Euclidean algorithm: 12 20 The GCD of 12 and 20 is 4

**Testcase 2:** The numbers entered by the user to calculate gcd using Euclidean algorithm are 18 and 144.

Enter two numbers to find gcd using Euclidean algorithm: 18 144 The GCD of 18 and 144 is 18

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:**

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