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 for two integers and .

Approach 1: GCD Using for Loop and if Statement

Algorithm

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

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: ,

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 and as input.
2. Initialize Variables: Set initially.
3. While Loop: Iterate until becomes 0.
• Update to the value of .
• Update to the remainder when is divided by .
4. Output: The final value of is the GCD of and .

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: ,

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.