Least Common Multiple (LCM)

Definition

Definition

The Least Common Multiple (LCM) algorithm is a computational method used to find the smallest positive integer that is divisible by two or more given integers

Explanation

The LCM algorithm works by identifying the prime factors of each given integer and then determining the product of the highest powers of all prime factors involved. This ensures that the resulting number is divisible by all given integers and is the smallest such number

Guidance

• Identify the prime factors of each given integer
• Determine the highest power of each prime factor among the given integers
• Multiply these highest powers together
• The result is the least common multiple of the given integers

Tips

• utilize efficient prime factorization techniques such as trial division or the Sieve of Eratosthenes
• use an optimized method to find the highest power of each prime factor, possibly through exponentiation or dynamic programming

Practice

Practice

LCM(nums):
  lcm = 1
  prime_factors = []

  for num in nums:
    factors = prime_factorization(num)
    update_prime_factors(prime_factors, factors)

  for factor in prime_factors:
    lcm *= factor

  return lcm

prime_factorization(num):
  factors = []
  divisor = 2

  while num > 1:
    while num % divisor == 0:
      factors.append(divisor)
      num /= divisor
    divisor += 1

  return factors

update_prime_factors(prime_factors, factors):
  for factor in factors:
    if prime_factors.count(factor) < factors.count(factor):
      prime_factors.append(factor)

Solution

package main

import (
	"math"
)

func euclideanAlgorithm(originalA, originalB int) int {
	a := int(math.Abs(float64(originalA)))
	b := int(math.Abs(float64(originalB)))

	if b == 0 {
		return a
	}
	return euclideanAlgorithm(b, a%b)
}

func leastCommonMultiple(a, b int) int {
	if a == 0 || b == 0 {
		return 0
	}
	return int(math.Abs(float64(a*b))) / euclideanAlgorithm(a, b)
}

public class Main {

  public static int euclideanAlgorithm(int originalA, int originalB) {
    int a = Math.abs(originalA);
    int b = Math.abs(originalB);

    return b == 0 ? a : euclideanAlgorithm(b, a % b);
  }

  public static int leastCommonMultiple(int a, int b) {
    if (a == 0 || b == 0) {
      return 0;
    }
    return Math.abs(a * b) / euclideanAlgorithm(a, b);
  }
}

function euclideanAlgorithm(originalA, originalB) {
  const a = Math.abs(originalA);
  const b = Math.abs(originalB);

  return b === 0 ? a : euclideanAlgorithm(b, a % b);
}

function leastCommonMultiple(a, b) {
  return a === 0 || b === 0 ? 0 : Math.abs(a * b) / euclideanAlgorithm(a, b);
}

import kotlin.math.abs

fun euclideanAlgorithm(originalA: Int, originalB: Int): Int {
    val a = abs(originalA)
    val b = abs(originalB)

    return if (b == 0) a else euclideanAlgorithm(b, a % b)
}

fun leastCommonMultiple(a: Int, b: Int): Int {
    return if (a == 0 || b == 0) {
        0
    } else {
        (abs(a * b) / euclideanAlgorithm(a, b))
    }
}

import math

def euclideanAlgorithm(originalA, originalB):
    a = abs(originalA)
    b = abs(originalB)

    return a if b == 0 else euclideanAlgorithm(b, a % b)

def leastCommonMultiple(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // euclideanAlgorithm(a, b)

fn euclidean_algorithm(original_a: i32, original_b: i32) -> i32 {
    let a = original_a.abs();
    let b = original_b.abs();

    if b == 0 {
        a
    } else {
        euclidean_algorithm(b, a % b)
    }
}

fn least_common_multiple(a: i32, b: i32) -> i32 {
    if a == 0 || b == 0 {
        0
    } else {
        (a.abs() * b.abs()) / euclidean_algorithm(a, b)
    }
}

function euclideanAlgorithm(originalA: number, originalB: number): number {
  const a = Math.abs(originalA);
  const b = Math.abs(originalB);

  return b === 0 ? a : euclideanAlgorithm(b, a % b);
}

function leastCommonMultiple(a: number, b: number): number {
  return a === 0 || b === 0 ? 0 : Math.abs(a * b) / euclideanAlgorithm(a, b);
}