C Program to Find GCD of Two Numbers– Euclidean Algorithm & For Loop

Learn how to write a C program to find the Greatest Common Divisor (GCD) using efficient algorithms. Includes full code, explanation, and steps.

What is GCD (Greatest Common Divisor)?

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. It’s commonly used in math, data science, and cryptography. In C programming, there are multiple ways to compute it efficiently.

Why Learn GCD in C?

Learning how to find the GCD in C helps beginners understand loops, conditionals, and algorithmic thinking. It's also a classic example of using logic to optimize computation.

Method 1: Using Euclidean Algorithm

How Euclidean Algorithm Works

Euclidean Algorithm is based on the principle that the GCD of two numbers doesn’t change if the larger number is replaced by its difference with the smaller number.

1. Take two numbers from the user.
2. Repeat until the second number becomes 0:
   • Replace the first number with the second number.
   • Replace the second number with the remainder of first divided by second.
3. The first number is the GCD.

C Program Using Euclidean Algorithm

#include <stdio.h>

// Function to compute GCD
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;

    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));

    return 0;
}

Method 2: Using For Loop

How It Works

This approach uses a for loop to iterate from 1 to the minimum of the two numbers. It checks every number to see if it divides both inputs without a remainder.

1. Read two integers from the user.
2. Find the smaller of the two numbers.
3. Use a for loop from 1 to the smaller number.
4. If a number divides both, store it as the current GCD.
5. Print the result after the loop ends.

Related Posts

C Program Using For Loop

#include <stdio.h>

int main() {
    int num1, num2, gcd;

    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    int min = (num1 < num2) ? num1 : num2;

    for(int i = 1; i <= min; i++) {
        if(num1 % i == 0 && num2 % i == 0) {
            gcd = i;
        }
    }

    printf("GCD of %d and %d is %d\\n", num1, num2, gcd);

    return 0;
}

Final Thoughts

Both methods are effective, but the Euclidean algorithm is more optimized and generally preferred in competitive programming. For learners, the loop method is easier to understand and helps solidify concepts of conditionals and loops.

FAQs

1. Can GCD be calculated for negative numbers?

Yes, but the sign is usually ignored. GCD is always considered a positive integer.

2. What if one number is zero?

The GCD of a number and zero is the absolute value of the non-zero number.

3. Is GCD and HCF the same?

Yes, GCD (Greatest Common Divisor) and HCF (Highest Common Factor) mean the same.

4. Can I use recursion to find GCD in C?

Absolutely. The Euclidean algorithm works beautifully with recursion too.

5. Why should I use Euclidean algorithm over loop method?

It’s faster and uses fewer iterations, especially for large numbers.