(정수론/파이썬) 최소공배수 구하는 두 가지 방법

# 최소공배수 구하는 두 가지 방법
# 관련 문헌: '친절한 수론 길라잡이' 35쪽 연습문제 5.4

# 관련함수
# my_lcm(a, b): 각기 a*b 사이의 배수를 구해서 교집합(공배수)을 구한 다음, 가장 작은 수를 돌려준다
# my_lcd(a, b): 각기 약수들을 찾아서 교집합(공약수)을 구한 다음, 그중 가장 작은 수를 돌려준다.
#              약수가 없을 경우, 모든 수의 공통 약수인 1을 돌려준다
# my_lcm2(a, b): 공약수를 찾아서 그것으로 a, b를 계속 나눈다. 공약수가 나오지 않을 때까지.
#                공약수가 없으면(서로소이면), 그때까지의 모든 나누는 수와 마지막 몫 두 개를 곱해서 돌려준다(최소공배수)

# 유클리드 호제법으로 두 수 a와 b (단 a > b) 의 최대공약수 구하기
def my_gcd(a, b):

    if a == b:
        return a
    if a < b:  # a > b 조건을 맞추기 위해 두 값을 맞바꾸기
        tmp = a
        a = b
        b = tmp
    
    r0 = a
    r1 = b
    for i in range(b): # 두 수 증 작은 수만큼 최대 반복
        r2 = r0 % r1 # 몫은 필요 없으므로 나머지만 구함
        
        if r2 == 0: # 나머지가 0이라면
            return r1 # 직전의 나머지가 최대공약수임
        # 값들을 한칸씩 shift 시켜서 다시 반복
        r0 = r1
        r1 = r2
        
# 약수 구하는 함수
def getDivisor(num):
  divisors = []
  root_num = round(num ** 0.5)
  # sqrt(num)까지만 조사하면 된다. 단, round로 하면 소수점 이하는 버리기 때문에 
  # 아래 range에서 돌릴 때는 +1을 해줘야 한다.
  
  for i in range(1, root_num+1):
    if num % i == 0:  # 나눠지면
      divisors.append(i)  # 제수(나누는 수)가 약수가 되고
      divisors.append(num // i)  # 그 몫도 약수가 된다

  # 구한 것을 set 함수를 통해 중복을 제거하고 다시 리스트로 바꾼 다음, 정렬해서 리턴한다.
  return sorted(list(set(divisors))) 


# 최소공배수 구하기
# my_lcm(a, b)라고 할 경우, 최소공배수는 a*b와 같거나 작다. a, b 가 서로소이면 최소공배수는
# a*b 이고, 공약수가 있을 경우, lcm(a, b) < a*b 이다.
# a의 배수를 a*b 이하에서 찾아서 나열하고, b의 약수를 a*b 이하에서 찾아서 나열해서,
# 교집합을 구하면 그것이 a*b 이하 공배수들인데, 그중에서 가장 작은 수가 최소공배수이다.
def my_lcm(a, b):
  ab = a * b
  a_multi = []
  for i in range(1, b+1):
    a_multi.append(a * i)
    
  b_multi = []
  for i in range(1, a+1):
    b_multi.append(b * i)
    
  common = set(a_multi) & set(b_multi) # 배수들의 교집합 즉, 공배수 찾기
  return min(list(common))  # 리스트형으로 바꿔 최소값을 리턴한다.
  

# 최소공약수를 구하는 함수 (1 제외)
def my_lcd(a, b):
  a_ = getDivisor(a)  # a의 약수를 모두 구한다
  b_ = getDivisor(b)  # b의 약수를 모두 구한다
  #print(a_)
  #print(b_)
  c_ = set(a_) & set(b_) # 두 약수들의 교집합을 구한다. 공약수들이 된다.
  
  if len(c_) == 1:  # 공약수가 1뿐이라면, 1을 반환: 최소공약수
    return min(c_)
  elif len(c_) > 1: # 공약수가 1외에도 있다면 1을 제거하고 가장 작은 수를 반환한다: 최소공약수
    return min(list(c_ - {1}))


# 최소공배수 구하기
# a, b 의 최소공배수로 나눠서 두 수가 서로소일 때까지 나누고, 
# 그 제수들(나누는 수)와 최종 몫들을 모두 곱하면 최소공배수가 된다. 중학교 1학년때 배우는...
def my_lcm2(a, b):
  if my_gcd(a, b) == 1: # a와 b가 서로소라면, a*b를 최소공배수로 반환
    return a * b

  # 이제 a, b의 공약수가 있다는 말이므로, 최소공약수를 구해서 a, b를 나눈다.
  divisors = []
  while True:
    lcd = my_lcd(a, b)  # 최소공약수를 구한다.

    if lcd != 1: # 최소공약수가 2 이상이라면
      a = a / lcd  # 그 수로 나눠서 몫을 새로 a라고 놓는다
      b = b / lcd  # 그 수로 나눠서 몫을 새로 b라고 놓는다
      divisors.append(lcd)  # 나누는 수(최소공약수)를 배열에 저장한다.
    else:                 # 최소공약수가 1이라면 더 이상 나눌 수 없으므로
      divisors.append(a)  # 최후의 몫들을 배열에 저장한다.
      divisors.append(b)
      total = 1
      for n in divisors: # 배열의 모든 원소들을 곱하여 리턴한다
        total *= n
      return int(total)
    
  
print (my_lcm(8, 12))
print (my_lcm(3, 7))
print (my_lcm(12, 66))
print (my_lcm(20, 30))
print (my_lcm(51, 68))
print (my_lcm(23, 18))
print(my_lcm(32383800, 8055))

print("")
print (my_lcm2(8, 12))
print (my_lcm2(3, 7))
print (my_lcm2(12, 66))
print (my_lcm2(20, 30))
print (my_lcm2(51, 68))
print (my_lcm2(23, 18))
print(my_lcm2(32383800, 8055))

결과:

24
21
132
60
204
414
5796700200

24
21
132
60
204
414
5796700200