두 정수의 최소 공배수를 계산하는 가장 효율적인 방법은 무엇입니까?

두 정수의 최소 공배수를 계산하는 가장 효율적인 방법은 무엇입니까?

---

두 정수의 최소 공배수를 계산하는 가장 효율적인 방법은 무엇입니까?

나는 방금 이것을 생각해 냈지만 분명히 원하는 것을 남깁니다.

int n=7, m=4, n1=n, m1=m;

while( m1 != n1 ){
    if( m1 > n1 )
        n1 += n;
    else 
        m1 += m;
}

System.out.println( "lcm is " + m1 );

---

의 최소 공배수 (LCM) a및 b그 최대 공약수 (GCD)로 나눈 그들의 제품 (예입니다 lcm(a, b) = ab/gcd(a,b)).

그래서 문제는 gcd를 찾는 방법입니다. 유클리드 알고리즘은 최대 공약수를 계산 일반적 방법이다. 고전적인 알고리즘을 직접 구현하는 것이 효율적이지만 이진 산술을 활용하여 조금 더 잘하는 변형이 있습니다. 참조 크 누스 의 " 컴퓨터 프로그래밍의 예술 " 볼륨 2, "Seminumerical 알고리즘"§ 4.5.2 .

---

최소 공배수는 둘 이상의 숫자 각각의 배수 인 최소 정수입니다.

세 정수의 LCM을 구하려면 다음 단계를 따르십시오.

  **Find the LCM of 19, 21, and 42.**

각 숫자에 대한 소인수 분해를 작성하십시오. 19는 소수입니다. 19를 인수 분해 할 필요가 없습니다.

21 = 3 × 7
42 = 2 × 3 × 7
19

각 소인수를 위의 소인수 분해에서 가장 많이 나타나는 횟수만큼 반복합니다.

2 × 3 × 7 × 19 = 798

21, 42, 19의 최소 공배수는 798입니다.

---

나는 " 최대 공배수에 의한 감소 "의 접근 이 더 빨라야한다고 생각한다. GCD 계산 (예 : Euclid 알고리즘 사용 )으로 시작한 다음 두 숫자의 곱을 GCD로 나눕니다.

---

최적화되었는지 여부는 모르겠지만 아마도 가장 쉬운 방법 일 것입니다.

public void lcm(int a, int b)
{
    if (a > b)
    {
        min = b;
        max = a;
    }
    else
    {
        min = a;
        max = b;
    }
    for (i = 1; i < max; i++)
    {
        if ((min*i)%max == 0)
        {
            res = min*i;
            break;
        }
    }
    Console.Write("{0}", res);
}

---

우선 최대 공약수를 찾아야합니다

for(int = 1; i <= a && i <= b; i++) {

   if (i % a == 0 && i % b == 0)
   {
       gcd = i;
   }

}

그 후 GCD를 사용하면 이와 같은 최소 공배수를 쉽게 찾을 수 있습니다.

lcm = a / gcd * b;

---

오버플로없이 아래의 C ++ 최고의 솔루션

#include <iostream>
using namespace std; 
long long gcd(long long int a, long long int b){        
    if(b==0)
        return a;
    return gcd(b,a%b);
}

long long lcm(long long a,long long b){     
    if(a>b)
        return (a/gcd(a,b))*b;
    else
        return (b/gcd(a,b))*a;    
} 

int main()
{
    long long int a ,b ;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;        
    return 0;
}

---

결과가 더 작은 숫자의 배수가 될 때까지 두 숫자 중 큰 숫자의 연속 배수를 취하십시오.

이거 효과가 있을지도 ..

   public int LCM(int x, int y)
   {
       int larger  = x>y? x: y,
           smaller = x>y? y: x,
           candidate = larger ;
       while (candidate % smaller  != 0) candidate += larger ;
       return candidate;
   }

---

C ++ 템플릿. 컴파일 시간

#include <iostream>

const int lhs = 8, rhs = 12;

template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc {
  calc() { }
};

template<int n> struct calc<n, 0, 0> {
  calc() { std::cout << n << std::endl; }
};

template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> {
  calc() { }
};

template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> {
  calc() { }
};

template<int n> struct lcm {
  lcm() {
    lcm<n-1>();
    calc<n>();
  }
};

template<> struct lcm<0> {
  lcm() {}
};

int main() {
  lcm<lhs * rhs>();
}

---

유클리드 GCD 코드 스 니펫

int findGCD(int a, int b) {
        if(a < 0 || b < 0)
            return -1;

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

---

두 숫자의 곱은 LCM * GCD 또는 HCF와 같습니다. 따라서 LCM을 찾는 가장 좋은 방법은 GCD를 찾고 제품을 GCD로 나누는 것입니다. 즉, LCM (a, b) = (a * b) / GCD (a, b)입니다.

참조 URL : https://stackoverflow.com/questions/3154454/what-is-the-most-efficient-way-to-calculate-the-least-common-multiple-of-two-int