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.

Your program should follow these steps:

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.

Input / Output