The GCD (Greatest Common Divisor) of two numbers is the largest number that divides both of them without leaving a remainder. For example, the GCD of 12 and 18 is 6. In C, there are multiple ways to find GCD using a for loop, while loop, recursion, and the Euclidean algorithm. Let's go through each one.
What Is GCD?
GCD is also known as HCF (Highest Common Factor). It is the greatest number that exactly divides two or more numbers.
- GCD of 12 and 8 is 4
- GCD of 100 and 75 is 25
- If one number is 0, the GCD is the other number
- To check GCD of two numbers first we need to read input from user. i.e ask user to enter two numbers
- Store those two numbers in two integer variables
- Check if number is factor of given two numbers by iterating in for loop.
- #include <stdio.h>
- // program to check gcd of two numbers in c
- // write a c program to find gcd of two integers
- // www.instanceofjava.com
- int main()
- {
- int number1, number2, i, gcd;
- // read input from user
- printf(" please enter any two numbers: ");
- scanf("%d %d", &number1, &number2);
- for(i=1; i <= number1 && i <= number2; ++i)
- {
- // checking if i is divisible by both numbers / factor of both numbers
- if(number1%i==0 && number2%i==0)
- gcd = i;
- }
- printf("GCD of %d and %d is %d", number1, number2, gcd);
- getch();
- }
Output:
- #include <stdio.h>
- // Function to compute Greatest Common Divisor using Euclidean Algorithm
- int gcd(int a, int b) {
- while (b != 0) {
- int temp = b;
- b = a % b;
- a = temp;
- }
- return a;
- }
- int main() {
- int num1, num2;
- // enter two numbers from the user
- printf("Enter two numbers to find their GCD: ");
- scanf("%d %d", &num1, &num2);
- // Ensure numbers are positive
- if (num1 < 0) num1 = -num1;
- if (num2 < 0) num2 = -num2;
- // Calculate and display the GCD
- int result = gcd(num1, num2);
- printf("The GCD of %d and %d is: %d\n", num1, num2, result);
- return 0;
- }
Explanation:
- Input:
- The user enters two numbers.
- Logic:
- The
findGCD function uses the Euclidean algorithm:- Replace a with b and b with a%b until b=0.
- The final value of a is the GCD.
- Output:
- The program prints the GCD of the two input numbers.
#1. GCD of Two Numbers Using for Loop
We loop from 1 to the smaller of the two numbers. Every time both numbers are divisible by i, we update gcd. The last value stored is the greatest common divisor.
#include <stdio.h>
int main() {
int n1, n2, i, gcd;
printf("Enter two integers: ");
scanf("%d %d", &n1, &n2);
for (i = 1; i <= n1 && i <= n2; ++i) {
if (n1 % i == 0 && n2 % i == 0)
gcd = i;
}
printf("GCD of %d and %d is %d", n1, n2, gcd);
return 0;
}
Output:
Enter two integers: 12 18
GCD of 12 and 18 is 6
#2. GCD of Two Numbers Using while Loop (Subtraction Method)
This approach uses the idea that if we keep subtracting the smaller number from the larger one, eventually both values become equal and that equal value is the GCD.
#include <stdio.h>
int main() {
int n1, n2;
printf("Enter two positive integers: ");
scanf("%d %d", &n1, &n2);
while (n1 != n2) {
if (n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
printf("GCD = %d", n1);
return 0;
}
Output:
Enter two positive integers: 48 18
GCD = 6
#3. GCD Using the Euclidean Algorithm (Most Efficient)
The Euclidean algorithm is the most efficient method. It works by repeatedly replacing the larger number with the remainder of dividing the two numbers until the remainder becomes 0. The last non-zero value is the GCD.
#include <stdio.h>
int main() {
int n1, n2, temp;
printf("Enter two integers: ");
scanf("%d %d", &n1, &n2);
while (n2 != 0) {
temp = n2;
n2 = n1 % n2;
n1 = temp;
}
printf("GCD = %d", n1);
return 0;
}
Output:
Enter two integers: 56 98
GCD = 14
#4. GCD Using Recursion
We can implement the Euclidean algorithm recursively. The base case is when a becomes 0 at that point we return b.
#include <stdio.h>
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int main() {
int n1, n2;
printf("Enter two integers: ");
scanf("%d %d", &n1, &n2);
printf("GCD of %d and %d is %d", n1, n2, gcd(n1, n2));
return 0;
}
Output:
Enter two integers: 36 60
GCD of 36 and 60 is 12
Comparison of All Methods
| Method |
Approach |
Best For |
| for loop |
Check every divisor from 1 to min(n1, n2) |
Beginners |
| while loop (subtraction) |
Repeatedly subtract smaller from larger |
Easy to understand |
| Euclidean algorithm |
Modulo-based replacement until remainder is 0 |
Best performance |
| Recursion |
Euclidean algorithm using function calls |
Clean, concise code |
Key Points to Remember
- GCD is also called HCF (Highest Common Factor)
- If either number is 0, the GCD is the other number
- The Euclidean algorithm is the fastest and most widely used method
- For negative numbers, convert to positive before computing GCD
- GCD is used in simplifying fractions, cryptography, and LCM calculations
All four approaches give the same result the choice depends on your use case. For interviews and competitive programming, go with the Euclidean algorithm or recursion. For beginners just learning loops, the for loop method is the easiest to follow.
