[Algorithm] Math - Least common multiple - 하고싶은거하는

최소 공배수(LCM)란?

두 정수의 최소 공배수(LCM)는 두 숫자를 모두 나눌 수 있는 가장 작은 양의 정수입니다. 즉, 두 정수가 나머지 없이 나눌 수 있는 가장 작은 숫자를 의미합니다.

예시:

6과 8의 최소 공배수는 24입니다. 왜냐하면 24는 6과 8 모두 나눌 수 있는 가장 작은 숫자이기 때문입니다.

LCM 계산 공식

최소 공배수를 계산하는 가장 효율적인 방법 중 하나는 최대 공약수(GCD)와 LCM의 관계를 사용하는 것입니다:

$ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} $

이 공식은 최대 공약수(GCD)를 계산하는 유클리드 알고리즘을 활용하여 최소 공배수를 효율적으로 구할 수 있습니다.

LCM의 사용 사례

스케줄링 문제: LCM은 두 반복 이벤트가 언제 다시 동시에 발생할지 찾는 데 도움을 줍니다. 예를 들어, 두 기계가 각각 x시간과 y시간 간격으로 작동할 때, LCM은 두 기계가 동시에 작동하는 시간을 계산하는 데 사용됩니다.
암호학: LCM은 RSA와 같은 특정 암호화 알고리즘에서 모듈러 연산에 사용됩니다.
수학 및 대수학: LCM은 서로 다른 분모를 가진 분수의 덧셈이나 뺄셈 문제를 해결할 때 자주 사용됩니다.
컴퓨터 시스템: LCM은 시스템 클록과 시간 동기화를 설계할 때, 작업이나 리소스를 동시에 관리하는 데 도움이 됩니다.

JavaScript에서의 LCM 예제

JavaScript를 사용하여 두 숫자의 LCM을 계산하는 방법은 다음과 같습니다:

function gcd(a, b) {
  while (b !== 0) {
    const remainder = a % b;
    a = b;
    b = remainder;
  }
  return a;
}

function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}

console.log(lcm(6, 8)); // 24 출력
console.log(lcm(12, 15)); // 60 출력

Rust에서의 LCM 예제

Rust에서 LCM을 계산하는 방법은 다음과 같습니다:

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let remainder = a % b;
        a = b;
        b = remainder;
    }
    a
}

fn lcm(a: u32, b: u32) -> u32 {
    (a * b) / gcd(a, b)
}

fn main() {
    println!("{}", lcm(6, 8));  // 24 출력
    println!("{}", lcm(12, 15));  // 60 출력
}

요약:

최소 공배수(LCM)는 두 정수가 나눌 수 있는 가장 작은 숫자입니다. LCM은 스케줄링, 암호학, 분수 계산 등의 수학적 연산에서 자주 사용됩니다. LCM과 GCD의 관계를 사용하면 유클리드 알고리즘을 활용하여 효율적으로 LCM을 계산할 수 있으며, JavaScript와 Rust에서 간단하고 효율적으로 구현할 수 있습니다.

Least Common Multiple (LCM)?

The Least Common Multiple (LCM) of two integers is the smallest positive integer that is divisible by both numbers. In other words, it is the smallest number that both integers divide without leaving a remainder.

For example:

The LCM of 6 and 8 is 24 because 24 is the smallest number divisible by both 6 and 8.

Formula to Calculate LCM

One of the most efficient ways to compute the LCM of two numbers is by using the relationship between the LCM and the Greatest Common Divisor (GCD):

$ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} $

This formula leverages the Euclidean algorithm for GCD calculation and uses it to find the LCM efficiently.

Where is LCM Used?

Scheduling Problems: LCM helps in finding when two repeating events will happen together again. For example, if two machines are scheduled to operate at intervals of x and y hours, the LCM helps in determining when both machines will be working simultaneously.
Cryptography: LCM is used in certain cryptographic algorithms like RSA for modulus calculation.
Mathematics and Algebra: LCM is often used in solving problems involving fractions, such as adding or subtracting fractions with different denominators.
Computer Systems: LCM helps in the design of system clocks and timekeeping to synchronize tasks or resources.

Example of LCM in JavaScript

Here’s how you can compute the LCM of two numbers using JavaScript:

function gcd(a, b) {
  while (b !== 0) {
    const remainder = a % b;
    a = b;
    b = remainder;
  }
  return a;
}

function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}

console.log(lcm(6, 8)); // Outputs 24
console.log(lcm(12, 15)); // Outputs 60

Example of LCM in Rust

Similarly, here’s an example of calculating the LCM in Rust:

fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let remainder = a % b;
        a = b;
        b = remainder;
    }
    a
}

fn lcm(a: u32, b: u32) -> u32 {
    (a * b) / gcd(a, b)
}

fn main() {
    println!("{}", lcm(6, 8));  // Outputs 24
    println!("{}", lcm(12, 15));  // Outputs 60
}

Summary:

The Least Common Multiple (LCM) is the smallest number that two integers divide without remainder. It is commonly used in scheduling, cryptography, and mathematical operations involving fractions. The LCM can be efficiently computed using the relationship between LCM and GCD, leveraging the Euclidean algorithm for GCD calculation. Both JavaScript and Rust offer simple and efficient ways to implement this.

[Algorithm] Math - Least common multiple

수학 최소공배수