백준 2982번
https://www.acmicpc.net/problem/2982

문제

---

생각하기

---

• 유클리드 호제법 문제이다.

  • 유클리드 호제법을 통해서 최대공약수와 최소공배수를 구할 수 있다.

• 최대공약수는 영어로 greatest common divisor(GCD) 이다

• 최소공배수는 영어로 least common multiple(LCM) 이다

동작

 
 private fun GCD(a: Long, b: Long): Long {
    if (a % b == 0L) return b
    return GCD(b, a % b)
} // End of GCD

특별한 설명은 필요하지 않은 것 같고,

GCD의 재귀 구현은 워낙 간단한지라 외워도 괜찮고 알아두면 가끔 유용하게 쓸 수 있는 것 같다.

코드

---

Kotlin

import java.util.*
import java.io.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val st = StringTokenizer(br.readLine())
    val N = st.nextToken().toLong()
    val M = st.nextToken().toLong()

    val gcd = GCD(N, M)
    val lcm = LCM(N, M, gcd)
    println(gcd)
    println(lcm)
} // End of main

private fun GCD(a: Long, b: Long): Long {
    if (a % b == 0L) return b
    return GCD(b, a % b)
} // End of GCD

private fun LCM(N: Long, M: Long, gcd: Long): Long {
    return (N * M) / gcd
} // End of LCM