# 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.