[백준 13241] 최소공배수

🔗문제 풀러가기
단계별로 풀어보기 단계 15의 2번째 문제이다.

문제 분석

유클리드 호제법을 이용하여 문제를 해결하였다.

코드

#include <iostream>
using namespace std;

long Lcm(long a, long b)
{
    long tempA = a, tempB = b;
    while (tempB != 0)
    {
        long c = tempA % tempB;
        tempA = tempB;
        tempB = c;
    }
    return (a * b) / tempA;
}

int main()
{
    int A, B;
    cin >> A >> B;

    cout << Lcm(A, B);
}

해석

1. 수를 입력받아 Lcm 함수를 실행해 최소 공배수를 구해 출력한다!

   Lcm 함수는 수를 입력받아 유클리드 호재법을 이용해
   최대 공약수를 구하여
   최소 공배수 = (두 수의 곱 / 최대 공약수)
   를 이용해 최소 공배수를 찾는 함수이다.