C Program to Find GCD and LCM of Two Numbers

This C program finds the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of two given numbers.

The GCD of two numbers is the largest positive integer that divides both of them without leaving a remainder. In other words, it is the highest common factor of the two numbers. The GCD is often used in simplifying fractions and performing operations on fractions. The LCM of two numbers is the smallest positive integer that is divisible by both numbers. It is the least common multiple of the two numbers. The LCM is used in problems involving multiple repetitions or cycles, such as finding the next common occurrence of events.

Problem Statement

Write a C program to find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers.

Input:

• Prompt the user to enter two integers.

Output:

• Print the calculated GCD and LCM.

Note:

• The GCD is the largest positive integer that divides both numbers without leaving a remainder.
• The LCM is the smallest positive integer that is divisible by both numbers.
• The program should handle cases where one or both of the numbers are negative or zero.
• The program should ensure that the output values are non-negative integers.
• You may assume that the input values are within the range of integers supported by the C programming language.

C Program to Find GCD and LCM of Two Numbers

#include <stdio.h>

// Function to calculate the GCD of two numbers
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// Function to calculate the LCM of two numbers
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int num1, num2;

    printf("Enter the first number: ");
    scanf("%d", &num1);

    printf("Enter the second number: ");
    scanf("%d", &num2);

    int gcd_result = gcd(num1, num2);
    int lcm_result = lcm(num1, num2);

    printf("The GCD of %d and %d is %d\n", num1, num2, gcd_result);
    printf("The LCM of %d and %d is %d\n", num1, num2, lcm_result);

    return 0;
}

How it Works

The program works by using two functions: gcd() and lcm(), to calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers, respectively.

1. The gcd() function:
   • This function takes two integer parameters, a and b, representing the two numbers for which we want to calculate the GCD.
   • It uses Euclid’s algorithm to find the GCD recursively. The algorithm states that the GCD of two numbers a and b is equal to the GCD of b and the remainder of a divided by b (i.e., a % b).
   • The function checks if b is zero. If it is, it means that a is the GCD, so it returns a.
   • Otherwise, it recursively calls the gcd() function with b and a % b as the new values of a and b, respectively, until b becomes zero.
   • Once the base case is reached, the function returns the GCD.
2. The lcm() function:
   • This function takes two integer parameters, a and b, representing the two numbers for which we want to calculate the LCM.
   • It calls the gcd() function to find the GCD of a and b.
   • The LCM of two numbers a and b can be calculated using the formula: LCM = (a * b) / GCD.
   • The function calculates the LCM by multiplying a and b and dividing the result by the GCD.
   • It returns the calculated LCM.
3. The main() function:
   • This is the entry point of the program.
   • It prompts the user to enter two numbers using the printf() function and reads the input using the scanf() function.
   • The input numbers are stored in variables num1 and num2.
   • It then calls the gcd() function with num1 and num2 as arguments and stores the result in the variable gcd_result.
   • Similarly, it calls the lcm() function with num1 and num2 as arguments and stores the result in the variable lcm_result.
   • Finally, it prints the calculated GCD and LCM using the printf() function.

By following these steps, the program calculates the GCD and LCM of the two input numbers and displays the results on the screen.

Input /Output

In this case, the program takes the input numbers 12 and 18. The GCD of 12 and 18 is 6, and the LCM is 36. The program then prints these values as output.