문 제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입 력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

24 18

출 력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

6
72

코 드

using System;
using static System.Console;
using System.Linq;

namespace algorithm
{
class Program
{
static void Main(string[] args)
{
int Max = 0;
int Min = 0;

            int[] num = ReadLine().Split(' ').Select(int.Parse).ToArray();

            Max = Gcd(num[0], num[1]);
            Min = (num[0] * num[1]) / Max;

            WriteLine(Max);
            WriteLine(Min);
        }

        static int Gcd(int a, int b)
        {
            int temp = 0;

            while (b != 0)
            {
                temp = a % b;
                a = b;
                b = temp;
            }

            return a;
        }
    }

}

비교코드 - 1

공 부

유클리드 호제법(Euclidean Algorithm)

• 최대 공약수를(GCD) 구하기 위한 알고리즘!
• 두 수 A, B가 주어졌을 때, 큰 수에서 작은 수를 빼고 한 쪽이 0이 될 때까지 계속해서 반복하는 알고리즘! (0 이전의 작은 수가 최대공약수)

번 외

• 최대 공약수 (Greates Common Divisor : GCD)
• 최소 공배수 (Least Common Multiple : LCM) -> (A x B) / 최대공약수