유클리드 호제법을 이용해 최대 공약수, 최소 공배수 구하기

최대 공약수 구하기

---

최대 공약수(GCD)

• GCD (Greatest Common Divisor)
• 수들의 공통 약수(공약수) 중 가장 큰 수

최대 공약수 구하는 방법

1. 각각의 수에 대한 공통 약수 찾기 (소인수 분해)

    def gcd(a, b):
      for i in range(min(a, b), 0, -1): # 가장 큰 약수를 구해야하기 때문에 내림차순 사용
        if a % i == 0 and if b % i == 0: # a, b를 나눌 수 있는 가장 큰 약수
          return i
   

   ex) 12, 8의 최대 공약수

        12 = 1 * 2 * 2 * 3   
        8 = 1 * 2 * 2 * 2   
        ∴ 최대 공약수 = 1 * 2 * 2 = 4   
   

   ex) 25, 20의 최대 공약수

        25 = 1 * 5 * 5    
        20 = 1 * 5 * 2 * 2   
        ∴ 최대 공약수 = 1 * 5 = 5
   

   ex) 5, 12의 최대 공약수

        5 = 1 * 5   
        12 = 1 * 2 * 2 * 3   
        ∴ 최대 공약수 = 1 (서로소 : 두 수의 최대 공약수가 1일 때 두 수를 서로소라 함)   
   

2. 유클리드 호제법
   • 큰 수에서 작은 수를 빼서 최종적으로 0이 나오는 수 구하기

      def gcd(a, b):
        while(a != b):  # a와 b값이 같을 경우 나머지가 0
          # 나머지가 0이 될 때까지 큰 수 에서 작은 수 빼기
          if(a > b): # 큰 수 결정  
            a -= b  # 큰 수 - 작은수 반복
          else: 
            b -= a
     
          return a # 나머지가 0일 경우 해당 수가 최대 공약수
     

   • 두 수 a, b 중 나머지 r과 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 성질 이용

       def gcd(a, b):
         a, b = max(a, b), min(a, b) # 큰 수, 작은 수 결정
               
         while (b != 0): # 큰 수 에서 작은 수로 나눈 나머지가 0이 될 때까지 실행
           a, b = b, a % b # 나머지 값으로 b를 나눠 주기 위해 변경
         return a # 나머지(b)가 0일 경우 a가 최대 공약수
     

     • a와 b의 최대 공약수 == b와 r의 최대 공약수 (a % b == r)

최소 공배수 구하기

---

최소 공배수(LCM)

• LCM (Least Common Multiple)
• 수들의 공통 배수(공배수) 중 가장 작은 수

최소 공배수 구하는 방법

1. 각각의 수에 대한 공약수와 서로소 찾기 (소인수 분해)

     def lcm(a, b):
    for i in range(max(a, b), a * b + 1): # 가장 작은 배수를 구해야하기 때문에 오름차순 사용
      if i % a == 0 and if i % b == 0: # a, b의 공통된 배수 중 가장 작은 수
        return i
   

   ex) 12, 6의 최소 공배수

        12 = 1 * 2 * 2 * 3   
        8 = 2 * 3   
        최소 공배수 = 2 * 2 * 3 = 12   
   

   ex) 12, 20의 최소 공배수

        12 = 1 * 2 * 2 * 3    
        20 = 1 * 5 * 2 * 2   
        최소 공배수 = 1 * 2 * 2 * 3 * 5 = 60   
   

   ex) 9, 24의 최소 공배수

        9 = 3 * 3   
        24 = 2 * 2 * 2 * 3   
        최소 공배수 = 2 * 2 * 2 * 3 * 3 = 72  
   

2. 유클리드 호제법
   • 두 수의 곱을 최대 공약수로 나누기

      def lcm(a, b):
        return int((a * b) / gcd(a, b)) # lcm = a * b / gcd
     

Reference

• khanacademy math