분류

  • 공약수 알고리즘
  • 공배수 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
def gcd(a, b):
    tmp = 0
    while b:
        tmp = a % b
        a = b
        b = tmp
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)

설명

유클리드 호제법은 두 다항식의 최대 공약수를 구하는 방법이다.

두 양의 정수 $a,b\ (a > b)$에 대하여 $a = bq+r\ (0 \leq r < b)$라 하면, $a,b$의 최대공약수 $b, r$의 최대공약수와 같다. $r=0$이라면, $a,b$의 최대공약수는 $b$가 된다.

수식1

즉, b == 0이 될때까지 재귀적으로 함수가 실행되는 것을 알 수 있다.

두 양의 정수 $a, b$에 대하여, 최대 공약수는 $L$ 최소 공배수는 $G$라 하면, $a \times b = L \times G$이 성립한다.

수식2