LCM을 찾는 C++ 프로그램

두 수의 최소공배수(LCM)는 두 수의 배수인 가장 작은 수입니다.

예:15와 9라는 두 개의 숫자가 있다고 가정해 보겠습니다.

15 = 5 * 3
9 = 3 * 3

따라서 15와 9의 LCM은 45입니다.

두 수의 최소공배수를 구하는 프로그램은 다음과 같습니다. -

예시

#include <iostream>
using namespace std;
int main() {
   int a=7, b=5, lcm;
   if(a>b)
   lcm = a;
   else
   lcm = b;
   while(1) {
      if( lcm%a==0 && lcm%b==0 ) {
         cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
         break;
      }
      lcm++;
   }
   return 0;
}

출력

The LCM of 7 and 5 is 35

위의 프로그램에서 변수 lcm는 두 숫자 중 큰 숫자로 설정됩니다. 이것은 다음 코드 스니펫을 사용하여 보여줍니다.

if(a>b)
lcm = a;
else
lcm = b;

이후 while 루프가 실행됩니다. 이 루프에서 LCM이 b와 마찬가지로 나누어지면 두 숫자의 LCM이며 표시됩니다. 그렇지 않은 경우 이 조건이 충족될 때까지 LCM이 증가합니다.

이것을 설명하는 코드 조각은 다음과 같습니다 -

while(1) {
   if( lcm%a==0 && lcm%b==0 ) {
      cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
      break;
   }
   lcm++;
}

두 숫자의 LCM을 찾는 또 다른 방법은 LCM 및 GCD 공식을 사용하는 것입니다. 이 공식은 두 숫자의 곱이 LCM과 GCD의 곱과 같음을 지정합니다.

a * b = GCD * LCM

수식을 이용하여 두 수의 최소공배수를 구하는 프로그램은 다음과 같다 -

예시

#include<iostream>
using namespace std;
int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
int main() {
   int a = 7, b = 5;
   cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
   return 0;
}

출력

The LCM of 7 and 5 is 35

위의 프로그램에서 LCM은 공식을 사용하여 구합니다. 먼저 gcd()를 사용하여 a 및 b의 GCD를 구합니다. 재귀함수입니다. 두 개의 매개변수, 즉 및 b가 있습니다. b가 0보다 크면 a가 main() 함수로 반환됩니다. 그렇지 않으면 gcd() 함수는 b 및 a%b 값으로 자신을 재귀적으로 호출합니다.

이것은 다음 코드 스니펫을 사용하여 보여줍니다.

int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}

GCD를 구한 후 공식을 사용하여 LCM을 계산합니다. 그러면 표시됩니다. 이것은 다음 코드 스니펫에 나와 있습니다.

cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);