GCD(Great Common Divisior), LCM(Least Common Multiple)

1. for문 활용

a, b = 12, 10

# GCD - 최대공약수
for i in range(min(a,b), 0, -1):
    if a % i == 0 and b % i == 0:
        gcd = i
        break

# LCM - 최소공배수
for i in range(a*b, 0, -1):
    if i % a == 0 and i % b == 0:
        lcm = i
        break

---

2. 유클리드 호제법 활용

a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

위 정의에 따라, r가 0일때의가 최대공약수가 된다. 또한, 두 수의 곱을 최대공약수로 나눈 값이 최소공배수가 된다. 

# GCD - 최대공약수
def GCD(a, b):
    while b > 0:
        a, b = a // b, a % b
    return a
    
# LCM - 최소공배수
def LCM(a, b):
    return (a*b) // GCD(a, b)

---

3. Math 라이브리러리 활용

import math

a,b = 12, 10
gcd = math.gcd(a, b)
lcm = math.lcm(a, b)