---

개요

---

📌 GCD (최대공약수)

• GCD (Greatest Common Divisor) : 최대공약수
  공통으로 나누어지는 수(약수) 중 가장 큰 수

---

1. 숫자를 하나씩 대입해서 구하는 방법

def solution(n, m):
    x = 0
    for i in range(min(n,m), 0, -1):
        if n % i == 0 and m % i == 0:
            x = i
            break
    return x

solution(125,112225) => 25

• for i in range(min(n, m), 0, -1)
  n, m 두 개의 숫자 중 작은 것인 min(n, m)부터 시작해서 1씩 줄여가면서 i를 결정
  i 는 작은수인 125부터 125, 124, 123 ... , 0 까지 내려간다.

• n % i == 0 and m % i == 0
  그리고 n과 m을 동시에 나누는 조건으로 둘 다 i 로 나누어 떨어지는 수를 x에 대입
  +) 둘 다 i 로 나누어 떨어진다 = 공약수
  +) 큰 수부터 1씩 줄여갔기 때문에 제일 먼저 찾은 수가 제일 큰 수 = 최대 공약수
  따라서 둘 다 i 로 나누어 떨어지는 때의 i를 x에 대입해 출력하면 x = 최대 공약수

---

2. 유클리드 호제법

• 정의

유클리드 호제법(- 互除法, Euclidean Algorithm):
2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除) 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.
위키백과, 우리 모두의 백과사전

• 요약하자면,
  n, m 이라는 두 수가 있을 때,
  n을 m으로 나눈 나머지인 r이 있다고 한다면,
  n, m의 최대공약수는 m과 r의 최대공약수와 같다.

def solution(n, m):
    x = 0
    while m > 0:
      n,m = m, n%m
    print (n)

solution(125,112225)

• while m > 0
  m이라는 숫자가 0보다 크면 계속해서 반복

• n, m = m, n % m
  나머지를 반복해서 구하기 위해 위 식을 반복
  (n % m (n과 m을 나눈 나머지)을 진행하며,
  값들을 계속해서 m 와 n % m로 교체하는 것)

• m 이 n과 나누어 떨어질 때 (n % m == 0) m 이 0보다 크지 않기 때문에 반복문 종료

• 그림 예시 참고 (+ 출처)

  

---

📌 LCM (최소공배수)

• LCM(Least Common Multiple) : 최소공배수
  두 수의 공통의 배수 중 가장 작은 수

---

1. 숫자를 하나씩 대입해서 구하는 방법

# 두 수의 최소공배수 구하는 함수 (숫자 하나씩 비교하며 구하기)
def solution(n, m):
    y = 0
    for i in range(max(n,m),(n*m)+1):
        if i % n == 0 and i % m == 0:
            y = i
            break
    return y

solution (12, 14)

• for i in range(max(n,m),(n*m)+1)
  n, m 두 개의 숫자 중 큰 것인 max(n, m)부터 시작해서 n과 m을 곱한 값까지 i를 결정
  i 는 큰 수인 14부터 15, 16, 17, ... , 168 까지 올라간다.

• i % n == 0 and i % m == 0
  그리고 i가 n과 m으로 동시에 나누어 떨어지는 수를 y에 대입
  +) i가 두 수로 나누어 떨어진다 = 공배수
  +) 두 수 중 큰 값부터 1씩 늘려갔기 때문에
  제일 먼저 찾은 수가 제일 작은 공배수 = 최소 공배수
  따라서 두 수로 나누어 떨어지는 때의 i를 y에 대입해 출력하면 y = 최소 공배수

---

2. 유클리드 호제법

• 두 수(n,m) 중 어느 한 수가 다른 한 수의 약수가 아니면,
  최소공배수 = n * m / 최대공약수

LCM = n * m / GCD

def GCD(n, m):
    x = 0
    while m > 0:
      n,m = m, n % m
    return n
n = 12
m = 14

LCM = (n * m) // GCD(n,m)
LCM

---

📌 파이썬 MATH 라이브러리

import math 
n = 12
m = 14

print(math.gcd(n,m))
print(math.lcm(n,m))

• 파이썬 math 라이브러리에서 최대공약수, 최소공배수 함수를 지원한다.
  math.gcd(), math.lcm()을 사용
  단, lcm함수가 파이썬 3.9버전부터 지원되니 참고!