[알고리즘- 파이썬] 최대공약수(유클리드 호제법), 최소공배수

최대 공약수,

최대 공약수란, 숫자 a, b가 주어졌을 떄, 공통되는 약수 중에서 최대 값을 의미한다.

최대공약수 구하기.

1. a, b 각각의 약수를 구해서 공통되는 약수중에서 가장 큰 값을 찾는 방법.

• 찾지 않아도 되는 약수들 까지 구해야하기 때문에 효율적이지 않다.

2. 유클리드 호제법

1. 유클리드 호제법이란,
   숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

   그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 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)