Understanding GCD (Greatest Common Divisor) Calculation in C

Introduction

The Greatest Common Divisor (GCD) is a fundamental concept in number theory, representing the largest positive integer that divides two or more integers without leaving a remainder. In this blog post, we’ll explore the computation of GCD in C using two different approaches: for loop with if statement and while loop with if…else statement.

What is GCD?

The GCD of two numbers is the largest positive integer that divides both numbers without a remainder. It is often denoted as $\text{GCD}(a,b)$ for two integers $a$ and $b$.

Approach 1: GCD Using for Loop and if Statement

Algorithm

1. Input: Take two integers $a$ and $b$ as input.
2. Initialize Variables: Set $gcd=1$ initially.
3. For Loop: Iterate from 1 to the smaller of $a$ and $b$.
   • Check if the current iteration value divides both $a$ and $b$.
   • If true, update $gcd$ to the current value.
4. Output: The final value of $gcd$ is the GCD of a and $b$.

C Code Example

#include <stdio.h>

// Function to calculate GCD using for loop and if statement
int calculateGCDForLoop(int a, int b) {
    int gcd = 1;

    for (int i = 1; i <= (a < b ? a : b); ++i) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }

    return gcd;
}

int main() {
    int num1, num2;

    // Input: Get two integers from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Calculate and print GCD using for loop and if statement
    printf("GCD using for loop: %d\n", calculateGCDForLoop(num1, num2));

    return 0;
}

Output Example

Input: $a=24$, $b=36$

Enter two integers: 24 36
GCD using for loop: 12

Approach 2: GCD Using While Loop and if…else Statement

Algorithm

1. Input: Take two integers $a$ and $b$ as input.
2. Initialize Variables: Set $gcd=1$ initially.
3. While Loop: Iterate until $b$ becomes 0.
   • Update $gcd$ to the value of $b$.
   • Update $b$ to the remainder when $a$ is divided by $b$.
4. Output: The final value of $gcd$ is the GCD of $a$ and $b$.

C Code Example

#include <stdio.h>

// Function to calculate GCD using while loop and if...else statement
int calculateGCDWhileLoop(int a, int b) {
    int gcd = 1;

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

    return gcd;
}

int main() {
    int num1, num2;

    // Input: Get two integers from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Calculate and print GCD using while loop and if...else statement
    printf("GCD using while loop: %d\n", calculateGCDWhileLoop(num1, num2));

    return 0;
}

Output Example

Input: $a=24$, $b=36$

Enter two integers: 24 36
GCD using while loop: 12

Conclusion

Computing the Greatest Common Divisor (GCD) is a foundational task in number theory and has applications in various mathematical and computational scenarios. The two approaches presented here showcase different methods for calculating the GCD using for loop with if statement and while loop with if…else statement.

Understanding the algorithms involved in GCD calculation enhances your programming skills and provides insights into how numbers can be manipulated efficiently. Whether you are a beginner learning the basics or an experienced programmer exploring number theory, mastering the computation of GCD is a valuable skill that finds applications in various domains.