[Python 유클리드 호제법] 최대 공약수, 최대 공배수 구하기

💡 공약수

여러 개의 정수가 공통으로 가지고 있는 약수

10 의 약수 : 1, 2, 5

5 의 약수 : 1, 5

공약수 : 1, 5

 

💡 GCD (Greatest Common Divisior) - 최대공약수

 

12의 약수 : 1, 2, 3, 4, 6, 12

8의 약수 : 1, 2, 4, 8

공통 : 1, 2, 4

8과 12의 최대 공약수  : 4

 

💡 LCM (Largest Common Multiple) - 최소공배수

두 수, 혹은 그 이상의 수들의 공통인 배수 중에서 가장 작은 수 

 

12의 배수 : 12, 24, 36, 48, 60

8의 배수 : 8, 16, 24, 32, 40, 48

8과 12의 최소 공배수  : 24

 

💡 실행 사진

 

 

💡 유클리드 호제법

비교대상 두 개의 자연수 n, m (단 n >m) 에서 n을 m으로 나눈 나머지를 r이라고 했을때

GCD(n, m) = GCD(m, r)과 같고 r이 0이면 그때 m이 최대공약수이다. 라는 원리를 활용한 알고리즘..

 

1. 숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미
2. 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을
   하면, 남는 a 값

 

💡 최대 공약수

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

 

💡 최소 공배수

def lcm(a, b):
    return a * b / gcd(a, b)

 

💡 전체 코드

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

def lcm(a, b):
    return a * b / gcd(a, b)
    
print(gcd(28, 14))
print(gcd(48, 24))

print(gcd(2, 4))
print(gcd(4, 8))