Find GCD and LCM of Two Numbers in C

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental concepts in number theory and widely used in programming for problem solving, simplification of fractions, and algorithm design.

This tutorial demonstrates how to find the GCD and LCM of two numbers in C using step-by-step algorithms and programs, with example input and output.

Problem Statement

Write a C program to find the GCD and LCM of two given integers.

Algorithm to Find GCD (Using Euclidean Method)

Step 1: Start the program.

Step 2: Input two integers, say a and b.

Step 3: Use the Euclidean algorithm:

- While b is not zero, assign temp = b, then b = a % b, a = temp.

Step 4: When b becomes zero, a contains the GCD.

Step 5: End.

Algorithm to Find LCM

Step 1: Start the program.

Step 2: Input two integers, a and b.

Step 3: Calculate LCM using the formula:

LCM = (a * b) / GCD(a, b)

Step 4: Print the LCM.

Step 5: End.

C Program to Find GCD and LCM

#include <stdio.h>

int main() {
    int a, b, x, y, gcd, lcm, temp;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    x = a;
    y = b;

    // Calculate GCD using Euclidean algorithm
    while(y != 0) {
        temp = y;
        y = x % y;
        x = temp;
    }
    gcd = x;

    // Calculate LCM using formula
    lcm = (a * b) / gcd;

    printf("GCD of %d and %d = %d\n", a, b, gcd);
    printf("LCM of %d and %d = %d\n", a, b, lcm);

    return 0;
}

Example Input/Output

Input:
Enter two integers: 12 18

Output:
GCD of 12 and 18 = 6
LCM of 12 and 18 = 36

Notes

- The Euclidean algorithm is an efficient method to compute the GCD of two numbers.

- LCM can be calculated using the relation: LCM(a, b) = (a * b) / GCD(a, b).

- Ensure integer multiplication does not overflow when calculating LCM for large numbers.

- Both GCD and LCM are always positive numbers.

Conclusion

Finding GCD and LCM is a fundamental skill in C programming and number theory. Understanding the Euclidean algorithm for GCD and using the formula for LCM allows you to solve many mathematical and programming problems efficiently.