[백준][Python] 1850번 LCM

https://www.acmicpc.net/problem/5347

 

코드

def gcd(n, m):
  while m > 0:
    n, m = m, n % m

  return n

t = int(input())

for _ in range(t):
  n, m = map(int, input().split())
  print(n * m  // gcd(n, m))

 

풀이

유클리드 호제법을 다시 복습하였는데 오랜만에 하느라 익숙하지가않았다. 그동안 너무 개발만해서 그런가 싶기도하고

 

반복문으로 구현된 유클리드 호제법 

def gcd(n, m):
  while m > 0:
    n, m = m, n % m

  return n

 

재귀문으로 구현된 유클리드 호제법 

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

 

최소공배수는 주어진 두 수의 곱을 최대공약수로 나누면 나온다.