39. 최대공약수와 최소공배수

 

위의 문제는 유클리드 호제법을 통해 최대공약수를 먼저 구하고,

 

두 수의 곱을 최대공약수로 나누는 방식으로 최소공배수를 구하면 된다.

 

유클리드 호제법은

 

 

위와 같이 큰 수에서 작은 수를 나눠 나머지를 구하고

 

큰 수를 작은 수로 교체 후, 작은 수를 나머지로 교체하여

 

큰 수에서 작은 수를 나누는 과정을 나머지가 0이 나올 때 까지 반복하면 된다.

 

using System;
using static System.Math;
public class Solution {
    public int[] solution(int n, int m) {
        int max = Math.Max(n,m);
        int min = Math.Min(n,m);
        
        while(min != 0)
        {
            int temp = max % min;
            max = min;
            min = temp;
        }
        
        return new int[] {max , n * m / max };
    }
}