[Algorithm] 유클리드 호제법 (최대 공약수, 최소 공배수)

 

최대 공약수

• 숫자 a,b가 주어졌을 때, 공통되는 약수 중 최대 값을 의미한다.
• 구하는 방법
  1. a,b 각각의 약수를 구해서 공통되는 약수 중 가장 큰 값을 찾는 방법
     
     • 찾지 않아도 되는 약수들까지 구해야하기 때문에 비효율적이다.
  2. 유클리드 호제법
     • 숫자 a,b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미한다.
     • 따라서, a를 b로 계속 나누어서 b에 a로 나눈 나머지를 대입시켜서 b가 0이 될 때까지 반복을 하면, 남는 a의 값이 바로 최대 공약수이다.

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

 

 

 

 

최소 공배수

• 서로 다른 수 a,b의 배수 중에서 공통되는 배수 중 가장 작은 값을 의미
• 최소 공배수는 a,b의 곱을 a,b의 최대 공약수로 나누면 나오게 된다.

( 최소 공배수 x 최대 공약수) = gcd^2 * m * n [ m,n은 서로소 ] => a * b

 

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