C++ Program to find LCM

Posted in C++ Tutorial

Updated on Oct 27, 2024

By Mari Selvan

👁️ 174 - Views

⏳ 4 mins

💬 1 Comment

Photo Credit to CodeToFun

🙋 Introduction

In the domain of programming, solving mathematical problems is a common and necessary task. One such problem is finding the Least Common Multiple (LCM) of two numbers.

The LCM is the smallest positive integer that is divisible by both numbers without leaving a remainder.

In this tutorial, we'll explore a C++ program that efficiently finds the LCM of two given numbers, utilizing the relationship between the greatest common divisor (GCD) and the LCM.

📄 Example

Let's take a look at the C++ code that achieves this functionality.

findGCD.cpp

Copied

#include <iostream>

// Function to find the GCD of two numbers
int findGCD(int num1, int num2) {
  while (num2 != 0) {
    int temp = num2;
    num2 = num1 % num2;
    num1 = temp;
  }
  return num1;
}

// Function to find the LCM of two numbers
int findLCM(int num1, int num2) {
  // LCM = (num1 * num2) / GCD(num1, num2)
  int gcd = findGCD(num1, num2);
  return (num1 * num2) / gcd;
}

// Driver program
int main() {
  // Replace these values with your desired numbers
  int number1 = 12;
  int number2 = 18;

  // Call the function to find the LCM
  int lcm = findLCM(number1, number2);

  std::cout << "LCM of " << number1 << " and " << number2 << " is: " << lcm << std::endl;

  return 0;
}

💻 Testing the Program

To test the program with different numbers, replace the values of number1 and number2 in the main function.

Output

LCM of 12 and 18 is: 36

Compile and run the program to see the LCM in action.

🧠 How the Program Works

The program defines a function findGCD to calculate the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm.
The function findLCM uses the GCD to find the LCM using the relationship: LCM = (num1 * num2) / GCD(num1, num2).
The driver program in the main function sets the values of number1 and number2, calls the findLCM function, and prints the result.

🧐 Understanding the Concept of LCM

Before delving into the code, let's take a moment to understand the concept of the Least Common Multiple (LCM).

The LCM of two numbers is the smallest positive integer that is divisible by both numbers without leaving a remainder.

For example, consider the numbers 12 and 18. The multiples of 12 are 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, ... The multiples of 18 are 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, ... The LCM of 12 and 18 is 36.

🎢 Optimizing the Program

While the provided program is effective, there are more efficient algorithms for finding the LCM. Consider exploring and implementing optimized algorithms such as the prime factorization method.

Feel free to incorporate and modify this code as needed for your specific use case. Happy coding!