LCM이 최대가 되도록 N보다 작거나 같은 세 정수 찾기 - C++

이 튜토리얼에서는 LCM의 개념을 기반으로 하는 프로그램을 작성할 것입니다. 제목에서 알 수 있듯이 LCM이 최대인 주어진 숫자보다 작거나 같은 세 숫자를 찾아야 합니다.

예를 들어 보겠습니다.

문제에 대해 알아보기 전에 LCM이 무엇인지 알아보고 이에 대한 프로그램을 작성해 보겠습니다.

LCM 는 숫자의 최소 공배수입니다. 최소공약수라고도 합니다. 두 개의 양수와 b의 경우 LCM은 와 b 모두로 균등하게 나눌 수 있는 가장 작은 정수입니다.

주어진 정수에 공통 인수가 없으면 LCM 주어진 숫자의 곱입니다.

예시

주어진 두 양수의 최소공배수를 구하는 프로그램을 작성해 봅시다.

#include <iostream>
using namespace std;
int main() {
   int a = 4, b = 5;
   int maximum = max(a, b);
   while (true) {
      if (maximum % a == 0 && maximum % b == 0) {
         cout << "LCM: " << maximum << endl;
         break;
      }
      maximum++;
   }
}

출력

위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

20

LCM이 무엇인지 살펴보고 두 양수의 LCM을 찾는 프로그램을 살펴보았습니다.

문제를 해결하는 단계를 살펴보겠습니다.

• 숫자가 홀수이면 최대 LCM이 있는 3개의 숫자는 n, n - 1,입니다. 및 n - 3 .

• 숫자가 짝수이고 GCM이 n인 경우 및 n - 3 1입니다. 최대 LCM이 있는 3개의 숫자는 n, n - 1입니다. , 및 n - 3 .

• 그렇지 않으면 최대 LCM이 있는 세 개의 숫자가 n - 1, n - 2입니다. , 및 n - 3 .

예시

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
void threeNumbersWithMaxLCM(int n) {
   if (n % 2 != 0) {
      cout << n << " " << (n - 1) << " " << (n - 2);
   }
   else if (__gcd(n, (n - 3)) == 1) {
      cout << n << " " << (n - 1) << " " << (n - 3);
   }
   else {
      cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
   }
   cout << endl;
}
int main() {
   int n = 18;
   threeNumbersWithMaxLCM(n);
   return 0;
}

출력

위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

17 16 15

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.