[C++/ 백준 13241번] 최소공배수

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

13241번: 최소공배수

 

해결방법

   유클리드 호제법으로 해결했다.

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
long long int euclid(long long int a, long long int b)
{
 
    if (a % b != 0)
    {

        return euclid(b, a % b);
    }
    else
    {
        return b;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
    
    long long int A, B;

  
        cin >> A >> B;

        long long int num;
   
        long long int cnt = 0;

        for (int j = 1; j <= (A > B ? A : B) ; j++)
        {
            if ((A % j == 0) && (B % j == 0))
            {
                cnt++;
            }
        }

        long long int max_div = euclid((A < B ? A : B), (A > B ? A : B));

 
        if (cnt == 1)
        {
            num = A * B;
        }
        else
        {
            num = (A * B / max_div);
        }

       

        cout << num << '\n';

    


    return 0;
}