백준 C# 49768592 최대공약수와 최소공배수

 

문제

 

두 수의 최대 공약수와 최소 공배수를 구하는 문제

 

 

 

해결

 

 

 

유클리드 호제법을  이용한 최대 공약수

두 자연수의 곱을 최대 공약수로 나눈 것이 최소공배수라는 공식을 이용

 

 

internal class E1259 //최대 공약수와 최소 공배수
{
    static void Main(string[] args)
    {
        int GCD(int a, int b)
        {
            if (b == 0) return a;
            else return GCD(b, a % b);
        }

        int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        if (input[0] < input[1]) input.Reverse();
        int g = GCD(input[0], input[1]);
        int l = input[0]* input[1] / g;

        Console.WriteLine($"{g} {l}");
    }
}

 

 

 

 

 

Ref.

https://seunghyum.github.io/algorithm/Euclidean-algorithm/#

[Algorithm] 유클리드 호제법(최대공약수 구하기) 공부