Lowest Common Multiple ( LCM )

LCM stands for "Least Common Multiple." It is a mathematical concept used to find the smallest positive integer that is divisible by two or more given integers. The LCM is often used in various mathematical calculations and is particularly useful when dealing with fractions, ratios, or solving problems involving multiple quantities.

Here's a detailed explanation of the LCM:

Definition: The LCM of two or more integers is the smallest positive integer that is evenly divisible by all of the given integers.

Finding the LCM: To find the LCM of two or more integers, you can use different methods such as prime factorization, listing multiples, or using the LCM formula.

Prime Factorization Method:

Express each given integer as a product of its prime factors.

Identify the common prime factors and their highest powers among all the integers.

Multiply the common prime factors with their highest powers to obtain the LCM.

Listing Multiples Method:

List the multiples of each integer until you find a common multiple.

The smallest common multiple among the listed multiples is the LCM.

LCM Formula:

If you have two integers, a and b, the LCM can be calculated using the formula: LCM(a, b) = (a * b) / GCD(a, b), where GCD represents the Greatest Common Divisor.

For example, let's find the LCM of 4 and 6 using the prime factorization method:

Prime factorization of 4: 2^2

Prime factorization of 6: 2 * 3

Common prime factors: 2 (highest power: 2)

LCM(4, 6) = 2^2 * 3 = 12

In this case, the LCM of 4 and 6 is 12.

The LCM has various applications, including simplifying fractions, finding common denominators, solving equations involving fractions, and finding the time it takes for multiple events or cycles to synchronize.

It's worth noting that the LCM is related to the concept of the Greatest Common Divisor (GCD). The GCD is the largest positive integer that divides evenly into two or more given integers. The relationship between LCM and GCD can be expressed as LCM(a, b) = (a * b) / GCD(a, b).

In C++, LCM (Least Common Multiple) is the smallest positive integer that is a multiple of two or more integers. Here's how you can calculate LCM in C++ using different methods:

Method 1: Using the formula

LCM can be calculated using the formula:

LCM(a, b) = (a * b) / GCD(a, b)

where GCD is the Greatest Common Divisor.


#include <iostream>
using namespace std;

// function to calculate GCD of two integers
int gcd(int a, int b) {
    // Euclidean algorithm
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// function to calculate LCM of two integers
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {

    int a = 12;
    int b = 18;

    cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << endl;

    return 0;
}

In this code, the gcd function calculates the GCD of two integers using the Euclidean algorithm. The lcm function uses the formula to calculate LCM of two integers using the gcd function. The main function initializes two integer values a and b, and calculates and outputs their LCM to the console.

Method 2: Using a loop

Another method to calculate LCM is to find the multiples of the two integers until the first common multiple is found.


#include <iostream>
using namespace std;

// function to calculate LCM of two integers
int lcm(int a, int b) {
    // find the maximum of two integers
    int m = max(a, b);

    for (int i = m; ; i += m) {
        if (i % a == 0 && i % b == 0) {
            return i;
        }
    }
}

int main() {

    int a = 12;
    int b = 18;

    cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << endl;

    return 0;
}

In this code, the lcm function initializes a variable with the maximum value of a and b, then loops over multiples of this maximum, checking if the multiple is divisible by both a and b. When the first common multiple is found, the function returns it as the LCM.

Method 3: Using recursion

LCM can also be calculated using recursion.


#include <iostream>
using namespace std;

// function to calculate GCD of two integers
int gcd(int a, int b) {
    // Euclidean algorithm
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// function to calculate LCM of two integers
int lcm(int a, int b) {
    static int m = a;
    if (m % a == 0 && m % b == 0) {
        return m;
    }
    m += gcd(a, b);
    return lcm(a, b);
}

int main() {

    int a = 12;
    int b = 18;

    cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << endl;

    return 0;
}

In this code, the gcd function calculates the GCD of two integers using the Euclidean algorithm. The lcm function initializes a static variable with the first integer value a, then adds gcd(a, b) to the variable until it becomes a common multiple of a and b. The function returns the variable as the LCM when the first common multiple is found.

These are different methods to calculate LCM in C++. All these methods work for any set of integer values.

PRACTICE PROBLEMS :

Ugly Number III

Number of Subarrays With LCM Equal to K