< 백준 BaekJoon : 13241번 최소공배수> C++

문제

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

 

코드

#include <iostream>
using namespace std;

void swap(long long int &numA, long long int &numB) {
  int temp = numA;
  numA = numB;
  numB = temp;
}

long long int findGcd(long long int numA, long long int numB) {
  int numC; // 나머지
  while (1) {
    numC = numA % numB;

    if (numC == 0)
      break;

    swap(numA, numB);
    numB = numC;
  }

  return numB;
}

long long int findLcd(long long int numA, long long int numB,
                      long long int numGcd) {
  long long int result = numA * numB / numGcd;
  return result;
}

int main() {
  long long int numA, numB;

  cin >> numA >> numB;
  if (numB > numA) {
    swap(numA, numB);
  }

  long long int numGcd = findGcd(numA, numB);
  long long int numLcd = findLcd(numA, numB, numGcd);
  cout << numLcd;
}

 

최대공약수를 먼저 찾고, 이를 바탕으로 최소공배수를 만들기

 

이 방법이 어렵다면 유클리드 호제법을 찾아 보시길