GCD, 유클리드 호제법, LCM

최대공약수(Greatest Common Divisor, GCD)

두 수 이상 여러 수의 공약수 중 최대인 수를 가리킴
최대공약수가 1이면 두 수는 서로소(coprime) 관계

✔️ 방법 1 - 기본적인 방법

def gcd(a, b):
	for i in range(min(a, b), 0, -1):
    	if (a % i == 0) & (b % i == 0):
        	return i

✔️ 방법 2 - math 라이브러리 사용

import math

def gcd(a, b):
	for i in range(min(a, b), 0, -1):
    	if (a % i == 0) & (b % i == 0):
        	return i

math.gcd(a, b)

✔️ 방법 2 - 유클리드 호제법

두 자연수의 최대공약수를 구하는 대표적인 알고리즘
* 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘

• 두 자연수 a와 `b가 있을 때,
• b가 0이 될 때까지 a를 b로 나눈 나머지를 구함
• a를 b로, b를 나머지로 업데이트함
• b가 0이 되면, 그 때의 a가 최대공약수!!

def euclidean(a, b):
    while b:
        a, b = b, a % b
    return a

최소공배수(Least Common Multiple, LCM)

두 자연수 중 어느 한 수가 다른 한 수의 약수가 아닐 경우,
최소공배수는 두 자연수의 곱에 최대공약수를 곱한 것
LCM = a * b * GCD