GCD of Two Numbers in C 4 Ways Explained with Examples

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.

2. #include <stdio.h>
3. // program to check gcd of two numbers in c 
4. // write a c program to find gcd of two integers
5. // www.instanceofjava.com
6. int main()
7. {
8.     int number1, number2, i, gcd;
9.     // read input from user
10.     printf(" please enter any two numbers: ");
11.     scanf("%d %d", &number1, &number2);
12. 
    
13.     for(i=1; i <= number1 && i <= number2; ++i)
14.     {
15.         // checking  if i is divisible by both numbers / factor of both numbers
16.         if(number1%i==0 && number2%i==0)
17.             gcd = i;
18.     }
19. 
    
20.     printf("GCD of %d and %d is %d", number1, number2, gcd);
21. 
    
22.     getch();
23. }

Output:

2. 
   
3. #include <stdio.h>
4. // Function to compute Greatest Common Divisor using Euclidean Algorithm
5. int gcd(int a, int b) {
6.     while (b != 0) {
7.         int temp = b;
8.         b = a % b;
9.         a = temp;
10.     }
11.     return a;
12. }
13. 
    
14. int main() {
15.     int num1, num2;
16. 
    
17.     // enter  two numbers from the user
18.     printf("Enter two numbers to find their GCD: ");
19.     scanf("%d %d", &num1, &num2);
20. 
    
21.     // Ensure numbers are positive
22.     if (num1 < 0) num1 = -num1;
23.     if (num2 < 0) num2 = -num2;
24. 
    
25.     // Calculate and display the GCD
26.     int result = gcd(num1, num2);
27.     printf("The GCD of %d and %d is: %d\n", num1, num2, result);
28. 
    
29.     return 0;
30. }
31. 
    

Explanation:

1. Input:
   • The user enters two numbers.
2. 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.
3. 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.