C Program to Determine the GCD of Two Numbers

by

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. This article will cover various C Program to Determine the GCD of Two Numbers. We will explore multiple examples, each demonstrating a different approach to solve the problem.

Prerequisites

Before we delve into the examples, ensure you have the following prerequisites:

  • A C compiler (such as GCC)
  • A text editor or IDE for writing your C code
  • Basic understanding of C programming concepts, especially loops and functions

1. Finding the GCD of Two Numbers

In this section, we will look at several methods to find the GCD of two numbers in C.

1.1 Using the Iterative Euclidean Algorithm

Example 1: Calculate GCD of Two Numbers Using the Iterative Euclidean Algorithm

This method uses the Euclidean algorithm iteratively to find the GCD of two numbers.

Code

C
#include <stdio.h>

int main() {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    printf("GCD is %d\n", a);

    return 0;
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Input the numbers: scanf reads two integers from the user.
  • Calculate GCD using the Euclidean algorithm: Use a while loop to repeatedly set b to a % b until b becomes 0.
  • Output the result: printf displays the GCD of the two numbers.

Output

C
Enter two integers: 48 18
GCD is 6

1.2 Using the Recursive Euclidean Algorithm

Example 2: Calculate GCD Using the Recursive Euclidean Algorithm

This method uses recursion to implement the Euclidean algorithm for finding the GCD.

Code

C
#include <stdio.h>

int gcd(int a, int b);

int main() {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    printf("GCD is %d\n", gcd(a, b));

    return 0;
}

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Declare a recursive function: int gcd(int a, int b) to compute the GCD.
  • Input the numbers: scanf reads two integers from the user.
  • Call the recursive function: gcd(a, b) computes the GCD recursively.
  • Output the result: printf displays the GCD of the two numbers.

Output

C
Enter two integers: 56 98
GCD is 14

1.3 Using the Binary GCD Algorithm

Example 3: Calculate GCD Using the Binary GCD Algorithm

This method uses the binary GCD algorithm (also known as Stein’s algorithm) to find the GCD.

Code

C
#include <stdio.h>

int binaryGCD(int a, int b);

int main() {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    printf("GCD is %d\n", binaryGCD(a, b));

    return 0;
}

int binaryGCD(int a, int b) {
    if (a == b)
        return a;
    if (a == 0)
        return b;
    if (b == 0)
        return a;

    if ((a % 2 == 0) && (b % 2 == 0))
        return 2 * binaryGCD(a / 2, b / 2);
    else if (a % 2 == 0)
        return binaryGCD(a / 2, b);
    else if (b % 2 == 0)
        return binaryGCD(a, b / 2);
    else if (a > b)
        return binaryGCD((a - b) / 2, b);
    else
        return binaryGCD((b - a) / 2, a);
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Declare a recursive function: int binaryGCD(int a, int b) to compute the GCD using Stein’s algorithm.
  • Input the numbers: scanf reads two integers from the user.
  • Call the recursive function: binaryGCD(a, b) computes the GCD recursively using the binary method.
  • Output the result: printf displays the GCD of the two numbers.

Output

C
Enter two integers: 48 18
GCD is 6

1.4 Using a Function with Iteration

Example 4: Calculate GCD Using a Function with Iteration

This method uses a function with iteration to find the GCD of two numbers.

Code

C
#include <stdio.h>

int gcd(int a, int b);

int main() {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    printf("GCD is %d\n", gcd(a, b));

    return 0;
}

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Declare a function: int gcd(int a, int b) to compute the GCD iteratively.
  • Input the numbers: scanf reads two integers from the user.
  • Call the function: gcd(a, b) computes the GCD iteratively.
  • Output the result: printf displays the GCD of the two numbers.

Output

C
Enter two integers: 72 120
GCD is 24

1.5 Using Prime Factorization

Example 5: Calculate GCD Using Prime Factorization

This method finds the GCD of two numbers by using their prime factorizations.

Code

C
#include <stdio.h>

int gcdUsingPrimeFactors(int a, int b);

int main() {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    printf("GCD is %d\n", gcdUsingPrimeFactors(a, b));

    return 0;
}

int gcdUsingPrimeFactors(int a, int b) {
    int gcd = 1;
    for (int i = 2; i <= a && i <= b; ++i) {
        while (a % i == 0 && b % i == 0) {
            gcd *= i;
            a /= i;
            b /= i;
        }
    }
    return gcd;
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Declare a function: int gcdUsingPrimeFactors(int a, int b) to compute the GCD using prime factorization.
  • Input the numbers: scanf reads two integers from the user.
  • Compute GCD using prime factorization: Iterate through possible factors and divide both numbers by the common factors.
  • Output the result: printf displays the GCD of the two numbers.

Output

C
Enter two integers: 30 45
GCD is 15

2. Conclusion

In this article, we explored various methods to calculate the GCD of two numbers in C: using the iterative Euclidean algorithm, using the recursive Euclidean algorithm, using the binary GCD algorithm, using a function with iteration, and using prime factorization. Each method demonstrates different aspects of handling mathematical operations and implementing algorithms in C programming. By understanding these methods, you can choose the one that best fits your specific needs and enhance your skills in algorithm implementation and modular programming in C.