According to Mathematics, the Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides the given integer values without remainder. For example, the GCD value of integer 8 and 12 is 4 because, both 8 and 12 are divisible by 1, 2, and 4 (remainder is 0) and the largest positive integer among the factors 1, 2, and 4 is 4.
The Greatest Common Divisor (GCD) is also known as the Highest Common Factor (HCF), or Greatest Common Factor (GCF), or Highest Common Divisor (HCD), or Greatest Common Measure (GCM). In this article we will show you, How to write a c program to find GCD of two numbers using For Loop, While Loop, Functions, and Recursion.
NOTE: In order to find the Greatest Common Divisor, we have to pass at least one non-zero value.
C Program to find GCD of Two Numbers using For Loop
This C program allows the user to enter two positive integer values and we are going to calculate the Highest Common Factor of those two values. Next, using the For loop in C Programming it will calculate the GCD.
CODE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//C program to find HCF of two numbers #include <stdio.h> int main() { int Num1, Num2, i, GCD; printf("Please Enter two integer Values \n"); scanf("%d %d", &Num1, &Num2); for(i = 1; i <= Num1 && i <= Num2; i++) { if(Num1 % i == 0 && Num2 % i == 0) GCD = i; } printf("GCD of %d and %d is = %d", Num1, Num2, GCD); return 0; } |
OUTPUT
ANALYSIS
- First printf statement will ask the user to enter two positive integer values.
- For loop will resist the i value, not to exceed the user specified values.
- In the next line we used the If Statement to check whether the remainder of Num1 % i and Num2 % i equals to zero or not.
C Program to find GCD of Two Numbers using While Loop
This C program allows the user to enter two positive integer values and we are going to calculate the Greatest Common Measure of those two values using the While Loop.
CODE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//C program to find HCF of two numbers #include <stdio.h> int main() { int Num1, Num2, Temp, GCD; printf("Please Enter two integer Values \n"); scanf("%d %d", &Num1, &Num2); while (Num2 != 0) { Temp = Num2; Num2 = Num1 % Num2; Num1 = Temp; } GCD = Num1; printf("GCD = %d", GCD); return 0; } |
OUTPUT
ANALYSIS
Within the while loop we are checking whether the second value is not equal to Zero or not, and if it is zero it will exit the while loop, otherwise it will start executing the statements inside the while loop.
C Program to find GCD of Two Numbers without using Temp
This program allows the user to enter two positive integer values and we are going to calculate the Greatest Common Measure of those two values without using the Temporary variable.
CODE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//C program to find HCF of two numbers #include <stdio.h> int main() { int Num1, Num2, GCD; printf("Please Enter two integer Values \n"); scanf("%d %d", &Num1, &Num2); if (Num1 == 0) { printf("GCD = %d", Num2); } while (Num2 != 0) { if (Num1 > Num2) { Num1 = Num1 - Num2; } else { Num2 = Num2 - Num1; } } GCD = Num1; printf("GCD = %d", GCD); return 0; } |
OUTPUT
C Program to find GCD of Two Numbers Using Functions
This program allows the user to enter two positive integer values and we are going to calculate the Greatest Common Divisor of those two values using Functions.
CODE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//C program to find HCF of two numbers #include <stdio.h> long gcd(long x, long y); int main() { int Num1, Num2; printf("Please Enter two integer Values \n"); scanf("%d %d", &Num1, &Num2); printf("GCD of %d and %d is = %d", Num1, Num2, gcd(Num1, Num2)); return 0; } long gcd(long x, long y) { if (x == 0) { return y; } while (y != 0) { if (x > y) { x = x - y; } else { y = y - x; } } return x; } |
OUTPUT
NOTE: If we create a function with Void then there is no need to return any value but, if we declared a function with any data type (int, float etc) then we have return something out from the function.
C Program to find GCD of Two Numbers using Recursion
This C program allows the user to enter two positive integer values and we are going to calculate the Greatest Common Divisor of those two values by calling the function recursively. Please refer Recursion in C for further reference
CODE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//C program to find HCF of two numbers #include <stdio.h> long gcd(long x, long y); int main() { int Num1, Num2; printf("Please Enter two integer Values \n"); scanf("%d %d", &Num1, &Num2); printf("GCD of %d and %d is = %d", Num1, Num2, gcd(Num1, Num2)); return 0; } long gcd(long x, long y) { if (y == 0) { return x; } else { return gcd(y, x % y); } } |
OUTPUT
ANALYSIS
When the compiler reaches to long gcd(long x, long y) line in main() program then the compiler will immediately jump to below function:
long gcd(long x, long y) {
In the above specified function, return gcd(y, x % y) statement will help the program to call the function Recursively with updated value and if you miss this statement then, after completing the first line it will terminate.
Lets see the If condition, if (y == 0) will check whether the number is equal to 0 or not. For Recursive functions it is very important to place a condition before using the function recursively otherwise, we will end up in infinite execution (Same like infinite Loop).
Please be careful 🙂
Thank you for Visiting Our Blog
I don't understand the analysis of else return gcd(y%x) ; in the last example