GCD of two numbers in C

The GCD of two numbers is the greatest whole number that divides both numbers evenly.

One of the most efficient algorithms to find the GCD of two numbers is the Euclidean algorithm.

This algorithm uses the fact that the GCD of two numbers also divides their difference and efficiently computes the GCD using repeated divisions.

Steps:

1Initialize:

Start with two numbers a and b.

---

2Swap if necessary:

Make sure a is greater than or equal to b.

If not, swap them.

---

3Divide:

Divide a by b and get the remainder r.

---

4Check remainder:

If r is zero, b is the GCD.

Otherwise, set a = b and b = r, then go back to step 3.

Example 1:

Numbers: a = 56, b = 98
Steps:
Initialize: a = 56, b = 98
Swap: a = 98, b = 56
Divide: 98 ÷ 56 = 1 R 42
Check R: a = 56, b = 42
Divide: 56 ÷ 42 = 1 R 14
Check R: a = 42, b = 14
Divide: 42 ÷ 14 = 3 R 0
GCD: 14

---

Example 2:

Numbers: a = 36, b = 48
Steps:
Initialize:a = 36, b = 48
Swap: a = 48, b = 36
Divide: 48 ÷ 36 = 1 R 12
Check R: a = 36, b = 12
Divide: 36 ÷ 12 = 3 R 0
GCD: 12

C Program to Find GCD:

// C Program to Find GCD
#include<stdio.h> 

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

// Main function to test the program
int main() {
    int num1, num2;

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

    int result = gcd(num1, num2);

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

    return 0;
}

Output:

Input: num1 = 56, num2 = 98
Output: GCD of 56 and 98 is 14
Input: num1 = 36, num2 = 48
Output: GCD of 36 and 48 is 12

This program uses the Euclidean algorithm to compute the GCD of two numbers entered by the user.