# C Program to Find GCD and LCM of Two Numbers using Euclidean Algorithm

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

## Problem statement

Write a C program that takes two numbers as input from the user and uses the Euclidean algorithm to find their greatest common divisor (GCD) and least common multiple (LCM). The program should then output the calculated GCD and LCM.

1. Prompt the user to enter two numbers.
2. Read the two numbers from the user.
3. Implement a function named `gcd` that takes two integer parameters and returns their GCD using the Euclidean algorithm.
4. Implement a function named `lcm` that takes two integer parameters and returns their LCM using the GCD.
5. In the `main` function, call the `gcd` and `lcm` functions with the user-provided numbers as arguments.
6. Output the calculated GCD and LCM to the console

Note:

Ensure that the program can handle positive integer inputs

## C Program to Find GCD and LCM of Two Numbers using Euclidean Algorithm

```#include <stdio.h>

// Function to calculate the GCD of two numbers using the Euclidean algorithm
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 two numbers: ");
scanf("%d %d", &num1, &num2);

int gcdResult = gcd(num1, num2);
int lcmResult = lcm(num1, num2);

printf("GCD: %d\n", gcdResult);
printf("LCM: %d\n", lcmResult);

return 0;
}
```

## How it works

1. The program starts by prompting the user to enter two numbers.
2. The `scanf` function is used to read the two numbers from the user and store them in variables `num1` and `num2`.
3. The program then calls the `gcd` function with `num1` and `num2` as arguments. The `gcd` function uses the Euclidean algorithm to recursively calculate the GCD of the two numbers.
• If `b` (the second number) is 0, it means that `a` (the first number) is the GCD, and the function returns `a`.
• Otherwise, the function calls itself with `b` as the first argument and `a % b` as the second argument.
4. The program assigns the returned GCD value from the `gcd` function to the variable `gcdResult`.
5. The program then calls the `lcm` function with `num1` and `num2` as arguments to calculate the LCM.
• The `lcm` function uses the formula `(a * b) / gcd(a, b)` to calculate the LCM.
6. The program assigns the returned LCM value from the `lcm` function to the variable `lcmResult`.
7. Finally, the program prints the calculated GCD and LCM values to the console using `printf` statements.

By utilizing the Euclidean algorithm to find the GCD and the LCM formula, the program efficiently calculates and displays the GCD and LCM of the given input numbers.