C Program to Find GCD of Two Numbers
Subject: PPS (Programming for Problem Solving)
Contributed By: Sanjay
Created At: February 3, 2025
Question:
Write a C C Program to Find GCD of Two Numbers.
Explanation Video:
Explanation:
- The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both numbers exactly.
- We use the Euclidean algorithm, which states that: GCD(a,b)=GCD(b,amod b)GCD(a, b) = GCD(b, a \mod b)
- Instead of recursion, we use a while loop:
Keep replacing a with b, and b with a % b.
Continue until b becomes 0. The remaining value of a is the GCD.
- Instead of recursion, we use a while loop:
Loop Explanation (Using Example: 48, 18)
Initial values: a = 48, b = 18
Loop runs while b ≠ 0:
temp = 18
b = 48 % 18 = 12
a = 18
Next iteration:
temp = 12
b = 18 % 12 = 6
a = 12
Next iteration:
temp = 6
b = 12 % 6 = 0
a = 6 (loop stops here)
Final Output:
GCD is 6
Source Code:
#include <stdio.h>
int main() {
int a, b, temp;
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
printf("GCD is %d\n", a);
return 0;
}
Input:
Enter two numbers: 48 18
Output:
GCD is 6