[자료구조&알고리즘] 유클리드 호제법 최대/최소공배수 구하기 (PYTHON, JAVA)

가장 많이 알고 있는 유클리드 호제법

• 2개의 자연수 최대공약수를 구하는 알고리즘의 하나
• 두 정수가 n과 m이고, n을 m으로 나눈 나머지가 r일 때, n과 m의 최대공약수는 m과 r의 최대공약수와 같다.

최소공배수

파이썬

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

자바

 public static int gcd(int n, int m)
 {
	if (m == 0) return n;
	return gcd(m, n % m);
 }

최대공배수

• x*y를 최대공약수로 나눈 몫이 최소공배수

파이썬

def lcm(x,y):
    res = (x*y) // gcd(x,y)
    return res

자바

 public static int lcm(int x, int y)
 {
	return x*y / gcd(x,y);
 }