The least common multiple (LCM) is a mathematical concept that is used to find the smallest number that is divisible by a set of given numbers. In this article, we will discuss the C++ algorithm for calculating the LCM of multiple numbers.
To begin with, let us understand what exactly is meant by the LCM of multiple numbers. In simple terms, LCM is the smallest positive integer that is divisible by all the given numbers. For example, the LCM of 3 and 5 is 15, as it is the smallest number that is divisible by both 3 and 5.
Now, let's get into the C++ algorithm for finding the LCM of multiple numbers. The algorithm can be divided into three steps:
Step 1: Find the prime factors of all the given numbers
To find the LCM, we need to first find the prime factors of all the given numbers. This can be done using a loop that runs from 2 to the given number. If a number is divisible by the current value of the loop, then it is a prime factor. We will store all the prime factors of each number in separate arrays.
Step 2: Create a frequency array
Next, we need to create a frequency array that will store the maximum occurrence of each prime factor. This can be done by comparing the frequency of each prime factor in the given numbers' prime factor arrays. For example, if the prime factor 2 occurs twice in the prime factor arrays of two given numbers, we will store the frequency as 2 in the frequency array.
Step 3: Calculate the LCM
Finally, we need to calculate the LCM using the prime factors and their frequencies. To do this, we will multiply all the prime factors with their corresponding frequencies and then take the product of all these values. The resulting number will be the LCM of the given numbers.
Let's see an example to understand this algorithm better. Suppose we have to find the LCM of 4, 6, and 8.
Step 1: Prime factors of 4: 2, 2
Prime factors of 6: 2, 3
Prime factors of 8: 2, 2, 2
Step 2: Frequency array: 3 for 2, 1 for 3
Step 3: LCM = 2 * 2 * 2 * 3 = 24
Hence, the LCM of 4, 6, and 8 is 24.
Now, let's see the C++ code for implementing this algorithm.
#include <iostream>
using namespace std;
// Function to find the LCM of two numbers
int LCM(int num1, int num2) {
// Find the prime factors of both numbers
int primeFactors1[100], primeFactors2[100];
int index1 = 0, index2 = 0;
// Find the prime factors of num1
for (int i = 2; i <= num1; i++) {
if (num1 % i == 0) {
primeFactors1[index1] = i;
num1 /= i;
index1++;
i--;
}
}
// Find the prime factors of num2
for (int i = 2; i <= num2; i++) {
if (num2 % i == 0) {
primeFactors2[index2] = i;
num2 /= i;
index2++;
i--;
}
}
// Create a frequency array
int frequency[100] = { 0 };
// Find the maximum frequency of each prime factor
for (int i = 0; i < index1; i++) {
int current = primeFactors1[i];
frequency[current] = max(frequency[current], count(primeFactors1, primeFactors1 + index1, current));
}
for (int i = 0; i < index2; i++) {
int current = primeFactors2[i];
frequency[current] = max(frequency[current], count(primeFactors2, primeFactors2 + index2, current));
}
// Calculate the LCM
int result = 1;
for (int i = 2; i < 100; i++) {
if (frequency[i] != 0) {
result *= pow(i, frequency[i]);
}
}
return result;
}
int main() {
// Input the numbers
int n;
cout << "Enter the number of numbers: ";
cin >> n;
int numbers[n];
cout << "Enter the numbers: ";
for (int i = 0; i < n; i++) {
