[C#] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수,
Solution을 완성해 보세요.
(배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환)

풀이

public class GCDLCMCalculator
{
    public static int[] Solution(int n, int m) {
        
        int smallNum = n <= m ? n : m;
        int largeNum = n >= m ? n : m;

        int greatestCommonDivisor = 0;
        int leastCommonMultiple = 0;

        for (int i = smallNum; i > 1; i--)
        {
            if (n % i == 0 && m % i == 0)
            {
                greatestCommonDivisor = i;
                break;
            }
        }
        
        greatestCommonDivisor = greatestCommonDivisor == 0 ? 1 : greatestCommonDivisor;

        if (greatestCommonDivisor == smallNum)
        {
            leastCommonMultiple =  largeNum;
        }
        else
        {
            leastCommonMultiple = ((largeNum / greatestCommonDivisor)  * (smallNum / greatestCommonDivisor)) * greatestCommonDivisor;   
        }
        
        int[] answer = new int[] {greatestCommonDivisor, leastCommonMultiple};
        return answer;
    }
}

준비 과정

• 두 개의 입력받은 숫자 중에서 큰 숫자 largeNum와 작은 숫자smallNum를 구분하여 저장

greatestCommonDivisor(최대공약수) 구하기

		int greatestCommonDivisor = 0;

        for (int i = smallNum; i > 1; i--)
        {
            if (n % i == 0 && m % i == 0)
            {
                greatestCommonDivisor = i;
                break;
            }
        }

• 최대공약수는 작은 숫자부터 1 사이의 숫자 중에서 결정됨
• smallNum에서 점차 줄어드는 반복문을 통해 해당 숫자가 입력받은 n과 m의 약수인지 판단
• 약수라고 판단되는 순간 반복문을 종료(약수 중에서 가장 큰 약수를 찾는 것이기 때문)

leastCommonMultiple(최소공배수) 구하기

        int leastCommonMultiple = 0;

        if (greatestCommonDivisor == smallNum)
        {
            leastCommonMultiple =  largeNum;
        }
        else
        {
            leastCommonMultiple = ((largeNum / greatestCommonDivisor)  * (smallNum / greatestCommonDivisor)) * greatestCommonDivisor;   
        }

• 구한 greatestCommonDivisor(최대공약수)가 주어진 숫자 중 작은 숫자와 같다면 smallNum이 largeNum의 약수이고, largeNum은 smallNum의 배수이므로
  둘 사이의 최소공배수는 largeNum이 됨

• 만약 그렇지 않다면 최대공약수를 포함하면서 최대 공약수로 두 숫자를 인수분해 하였을 때 남는 요소를 모두 포함하는 요소가 최소공배수가 된다.

  Ex) n = 24, m = 36
  최대공약수 = 12
  n = 최대공약수 * 2
  m = 최대공약수 * 3
  최소공배수 = 최대공약수 * 2 * 3

• 위와 같은 방식을 사용하면 두 숫자를 약수로 가지는 조건을 성립한 가장 작은 수 = 최소공배수를 구할 수 있다.