# GCD of two numbers in C

0 177

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

1**Initialize:
**

Start with** two numbers** **a **and **b**.

2**Swap if necessary:
**

Make sure a is **greater** than or** equal** to **b**.

If not, **swap them**.

3**Divide:
**

Divide a by** b** and get the** remainder r**.

4**Check 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 = 98Steps:Initialize:a = 56, b = 98Swap:a = 98, b = 56Divide:98 ÷ 56 = 1 R 42Check R:a = 56, b = 42Divide:56 ÷ 42 = 1 R 14Check R:a = 42, b = 14Divide:42 ÷ 14 = 3 R 0GCD:14

**Example 2:
**

Numbers:a = 36, b = 48Steps:Initialize:a = 36, b = 48Swap:a = 48, b = 36Divide:48 ÷ 36 = 1 R 12Check R:a = 36, b = 12Divide:36 ÷ 12 = 3 R 0GCD: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.

Share:

## Comments

Waiting for your comments