이번 글에서는 최대공약수와 최소공배수를 찾는 알고리즘에 살펴보도록 하겠습니다. 이 글은 위키피디아와 이곳을 참고하였습니다. 그럼 시작하겠습니다.

최대공약수

$x$의 약수이면서 $y$의 약수인 수 중 최대값을 $x$와 $y$의 최대공약수라고 합니다. 최대공약수를 구하는 가장 간단한 방법은 1~($x$와 $y$ 중 작은 값) 범위에서 공약수(둘 모두 나머지가 0)를 모두 구해 이 가운데 최대값을 구하는 방법입니다.

그런데 우리는 최대값에만 관심이 있으므로 역순, 즉 ($x$와 $y$ 중 작은 값)~1까지의 범위를 탐색해 가장 처음 발견한 공약수를 최대공약수로 삼으면 더 좋을 것입니다. 파이썬으로 구현한 코드는 다음과 같습니다.

def computeHCF(x, y):
    # 두 수 가운데 작은값 찾기
    if x > y:
        smaller = y
    else:
        smaller = x
    # smaller~1까지의 범위를 역순으로 탐색
    for i in range(smaller + 1, 1, -1):
        # 처음 공약수를 발견하면 그 수를 hcf에 저장하고
        # 탐색 종료
        if ((x % i == 0) and (y % i == 0)):
            hcf = i
            break
    return hcf

유클리드 호제법(Euclidean algorithm)을 이용할 수도 있습니다. 1071과 1029의 최대공약수를 유클리드 호제법을 활용해 계산하면 다음과 같습니다.

(1) 1071은 1029로 나누어 떨어지지 않기 때문에 1071을 1029로 나눈 나머지를 구한다 : 42

(2) 1029는 42로 나누어 떨어지지 않기 때문에 1029를 42로 나눈 나머지를 구한다 : 21

(3) 42는 21로 나누어 떨어진다

(4) 1071과 1029의 최대공약수는 21이다.

유클리드 호제법으로 최대공약수를 구하는 파이썬 코드는 다음과 같습니다.

def computeHCF_euc(x, y):
   # y가 0이 될 때까지 반복
   while(y):
       # y를 x에 대입
       # x를 y로 나눈 나머지를 y에 대입
       x, y = y, x % y
   return x

최소공배수

$x$와 $y$의 공통된 배수 가운데 최소값을 최소공배수라고 합니다. 최소공배수를 구하는 가장 간단한 방법은 다음과 같습니다.

def lcm(x, y):
   # 두 수 가운데 큰 값 찾기
   if x > y:
       greater = x
   else:
       greater = y
   # greater의 값을 1씩 증가시키면서 반복
   while(True):
       # greater가 x와 y로 모두 나누어 떨어질 경우
       # 최소공배수이므로 이 값을 lcm에 저장하고 반복문 종료
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
   return lcm

최대공약수와 최소공약수 사이의 관계와 유클리드 호제법을 활용해 구할 수도 있습니다. 예컨대 $x=ab$이고 $y=bc$라면 $x$와 $y$의 최대공약수는 $b$, 최소공배수는 $abc$입니다. $xy=ab^2c$이므로 이를 최대공약수 $b$로 나눠주면 최소공배수를 구할 수 있습니다.

우리는 이미 유클리드 호제법을 활용해 최대공약수를 구하는 알고리즘을 구현해 놓았으므로 이를 다시 활용합니다. 다음과 같습니다.

def lcm(x, y):
   lcm = (x*y)//computeHCF_euc(x,y)
   return lcm