Find the GCD using Loops in C

In C, we can find the Greatest Common Divisor (GCD) of two numbers using loops such as the for loop and while loop. The GCD of two numbers is the largest integer that divides both numbers without leaving a remainder. In this tutorial, we will explore different ways to compute the GCD using loops in C.

Examples to Find GCD using Loops

1. Finding GCD Using a for Loop

In this example, we will use a for loop to find the GCD of two numbers by checking all possible divisors from 1 to the smallest of the two numbers.

main.c

</>
Copy
#include <stdio.h>

int main() {
    int num1, num2, gcd = 1;

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

    int min = (num1 < num2) ? num1 : num2;

    for (int i = 1; i <= min; i++) {
        if (num1 % i == 0 && num2 % i == 0) {
            gcd = i;
        }
    }

    printf("GCD of %d and %d is %d\n", num1, num2, gcd);
    return 0;
}

Explanation:

  1. We declare integer variables num1, num2, and gcd, initializing gcd to 1.
  2. The user inputs two numbers using scanf().
  3. We determine the smaller number using the conditional expression (num1 < num2) ? num1 : num2.
  4. The for loop iterates from 1 to the smaller number.
  5. Inside the loop, we check if both numbers are divisible by i.
  6. If the condition is met, we update gcd to i.
  7. Finally, we print the GCD.

Output:

Enter two numbers: 12 18
GCD of 12 and 18 is 6

2. Finding GCD Using a while Loop

In this example, we will use a while loop to compute the GCD using the Euclidean algorithm, which repeatedly subtracts the smaller number from the larger one.

main.c

</>
Copy
#include <stdio.h>

int main() {
    int num1, num2;

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

    while (num1 != num2) {
        if (num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }

    printf("GCD is %d\n", num1);
    return 0;
}

Explanation:

  1. We declare two integer variables, num1 and num2.
  2. The user inputs two numbers using scanf().
  3. The while loop runs until num1 and num2 become equal.
  4. In each iteration, we subtract the smaller number from the larger one.
  5. Once both numbers are equal, the GCD is found, and we print the result.

Output:

Enter two numbers: 48 18
GCD is 6

3. Finding GCD Using the Modulus Operator

In this example, we will use the Euclidean algorithm with the modulus operator to compute the GCD efficiently.

main.c

</>
Copy
#include <stdio.h>

int main() {
    int num1, num2;

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

    while (num2 != 0) {
        int temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }

    printf("GCD is %d\n", num1);
    return 0;
}

Explanation:

  1. We declare two integer variables, num1 and num2.
  2. The user inputs two numbers using scanf().
  3. The while loop runs until num2 becomes 0.
  4. In each iteration, we store num2 in a temporary variable.
  5. We update num2 as num1 % num2.
  6. num1 takes the previous value of num2.
  7. When num2 becomes 0, num1 holds the GCD.

Output:

Enter two numbers: 56 98
GCD is 14

Conclusion

In this tutorial, we explored three different methods to compute the GCD using loops in C:

  1. Using a for loop to check all divisors.
  2. Using a while loop with subtraction (Euclidean algorithm).
  3. Using a while loop with the modulus operator for efficiency.