최대공약수와 최소공배수<유클리드 호제법>

이 문제는 유클리드 호제법을 사용하여 해결하는 문제였다. 유클리드 호제법은 최대공약수를 구하는 대표적인 알고리즘 중 하나이다.

처음에는 생소해서 원론을 찾아봤는데..

유클리드의 원론 제7권에는 다음과 같은 내용이 기술되어 있었다..

두 개의 자연수 또는 정수 a와 b에 대해서, a를 b로 나눈 나머지를 r이라고 하겠습니다. (단, a는 b보다 큽니다.) 그러면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이러한 성질에 따라, b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복합니다. 이 과정을 나머지가 0이 되었을 때까지 반복합니다. 그러면 마지막으로 사용한 나누는 수가 a와 b의 최대공약수가 됩니다.

이 알고리즘은 유클리드의 원론에서 가장 오래된 알고리즘으로 알려져 있으며, 기원전 300년경에 기술되었습니다. 이 알고리즘은 최대공약수를 구하는 가장 효율적인 방법 중 하나로 널리 사용되고 있다고한다..

문제

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

입력

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

출력

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

예제 입력 1

24 18

예제 출력 1

6
72

코드

---

fun gcd(a: Int, b:Int): Int = if(b != 0) gcd(b, a % b) else a

fun main() {
    val iput = readLine()
    val (num1,num2)=iput?.split(" ")?.map{it.toInt()}?: listOf(0,0)

    println(gcd(num1,num2))
    println(num1*num2/gcd(num1,num2))
}

유클리드 호제법을 재귀함수를 통해 이용해 gcd(최대공약수)함수를 구현했다.

최대공약수는 두수의곱을 최대공약수로 나누는 것을 통해 구하였다.

이 또한 공부가 필요한 문제이다..!!