Lets write a C program to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two positive integer numbers input by the user using Euclid’s Algorithm and by using Recursive function call logic.
Related Read:
C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm
Recursive Functions In C Programming Language
Page Contents
If user inputs 2 numbers n1 and n2, reduce the bigger number by modulo dividing it by the smaller number. For example, if n1 is greater than n2, then reduce the value of n1 by replacing it with n1%n2.
Assume that we’ve a function gcd() which returns gcd of 2 numbers passed to it. Ex: gcd(n1, n2);
According to Euclid’s Algorithm, we’ll get the same gcd if we reduce the bigger number by modulo dividing it by smaller number.
If n1 > n2 we need to pass gcd(n1%n2, n2);
If n2 > n1, we need to pass gcd(n1, n2%n1);
We need to recursively execute above 2 lines of logic until either n1 is 0 or until n2 is 0. If n1 is 0, then value present in n2 is the gcd of (n1,n2). If n2 is 0, then value present in n1 is the gcd of (n1,n2).
#include<stdio.h> int gcd(int, int); int main() { int num1, num2; printf("Enter 2 positive integer numbers\n"); scanf("%d%d", &num1, &num2); printf("\nGCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2)); return 0; } int gcd(int n1, int n2) { if(n1 == 0) return n2; if(n2 == 0) return n1; if(n1 > n2) return gcd(n1%n2, n2); else return gcd(n1, n2%n1); }
Output 1:
Enter 2 positive integer numbers
1980
1617
GCD of 1980 and 1617 is 33.
Output 2:
Enter 2 positive integer numbers
15
20
GCD of 15 and 20 is 5.
Lets assume that user has entered n1 = 1980 and n2 = 1617
n1 | n2 | Biggest No | Evaluate | Function Call |
---|---|---|---|---|
1980 | 1617 | 1980 | gcd(1980 % 1617, 1617) | gcd(363, 1617) |
363 | 1617 | 1617 | gcd(363, 1617 % 363) | gcd(363, 165) |
363 | 165 | 363 | gcd(363 % 165, 165) | gcd(33, 165) |
33 | 165 | 165 | gcd(33, 165 % 33) | gcd(33, 0) |
In above table gcd(33, 0) gets called, since n2 = 0, our program returns value of n1 as gcd, which is 33.
So GCD of 1980 and 1617 is 33.
#include<stdio.h> int gcd(int, int); int main() { int num1, num2; printf("Enter 2 positive integer numbers\n"); scanf("%d%d", &num1, &num2); printf("GCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2)); return 0; } int gcd(int n1, int n2) { if(n1 == 0) return n2; if(n2 == 0) return n1; return( (n1 > n2) ? gcd(n1%n2, n2) : gcd(n1, n2%n1) ); }
Output 1:
Enter 2 positive integer numbers
1980
1617
GCD of 1980 and 1617 is 33.
Know more about ternary operator or conditional operator, watch a separate video tutorial: Ternary Operator / Conditional Operator In C.
For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List
For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert