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

유클리드 호제법

• 최대 공약수를 구하는 알고리즘
• 응용으로는 확장 유클리드 알고리즘이 있다.

// kotlin

fun gcd(a: Int, b: Int): Int {
    var x = a
    var y = b
    while(y > 0) {
        val mod = x % y
        x = y
        y = mod
    }

    return x
}

# python

def gcd(a, b):
	while b > 0:
		a, b = b, a % b
	return a

최소 공배수

• 최대 공약수 함수를 이용해서 최소 공배수를 구함

// koltin

fun lcm(a: Int, b: Int): Int = a * b / gcd(a, b)

# python

def lcm(a, b):
	return a * b / gcd(a, b)