최대공약수 & 최소공배수

유클리드 호제법을 이용하여 푼다!

유클리드 호제법 : 두 수의 최대공약수를 구하는 알고리즘`

1. 주어진 두 값에서 큰 값 % 작은 값 연산을 하여 나머지를 구한다.
2. 나머지가 0이 아니라면, 작은 값 % 나머지 값을 계속 진행한다.
3. 나머지가 0이 되면, 마지막 계산에서 나누는 수로 사용된 숫자가 두 수의 최대공약수가 된다.

반복문 사용

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

재귀함수 사용

def gcd(a, b):
  if (b>a) : a,b = b,a  
  return b if not(a%b) else gcd(b, a%b)

최소공배수

주어진 두 값을 곱한 다음 최대공약수로 나누어준다.