[C++] 백준 2609 최대공약수와 최소공배수 (유클리스 호제법)

#include <iostream>
 
int gcd(int iSmall, int iBig) 
{
	int iRemain = iBig % iSmall;
 
	while (iRemain) 
    {
        iBig = iSmall;
        iSmall = iRemain;
		iRemain = iBig % iSmall;
	}
 
    return iSmall;
}
 
int main()
{
    int iFirst = 0;
    int iSecond = 0;
 
    std::cin >> iFirst >> iSecond;
 
    if (iFirst > iSecond)
    {
        int iTemp = iFirst;
        iFirst = iSecond;
        iSecond = iTemp;
    }
 
    int iMin = gcd(iFirst, iSecond);
    int iMax = iFirst * iSecond / iMin;
 
    std::cout << iMin << "\n" << iMax;
 
    return 0;
}

최근에 면접준비하다가 다 떨어지고(ㅋㅋㅋ....) 다시 코테로 돌아왔다...

솔브드에 CLASS라는 게 있는지 몰라서 백준만 풀다가 CLASS로 넘어왔다.

문제 자체는 어렵지 않은데 수학적 개념이 들어가있어서 올리는 걸로

최대공약수는 두 값 중 큰 값을 작은 값으로 나눈 것을 계속해서 나누면 나온다. 말로는 설명이 어려워서 아래 작성한다.

2335 와 300의 최대 공약수

2335 % 300 = 235

300 % 235 = 65

235 % 65 = 40

65 % 40 = 25

40 % 25 = 15

25 % 15 = 10

15 % 10 = 5

10 % 5 = 0

이렇게 마지막으로 남는 5가 최대 공약수가 된다.

 

최소공배수는 큰 값 X 최소 값 / 최대공약수 (소인수분해를 해보면 바로 답이 나온다)