최대공약수, 최소공배수 w. 유클리드 호제법

• 최대공약수 GCD(greatest common divisor)

  • 유클리드 호제법: x와 y의 최대공약수 == y와 r의 최대공약수 (r = x%y)
    e.g. x = 10, y = 12

        x    y    r
       10 % 12 == 10  
        y    r
       12 % 10 == 2
       반복해서
       10 % 2 == 0
    
       r이 0이 될 때의 y가 최대공약수, 따라서 2가 최대공약수

  • 코드

      def GCD(x,y):
          while(y):
              x, y = y, x%y
          return x

  • 내장함수 이용

      import math
      math.gcd(x,y)

• 최소공배수 LCM(least common multiple)
  • (x*y) / (x와 y의 최대공약수)
  • 코드

      def LCM(x, y):
          result = (x*y)//GCD(x,y)
          return result

  • 내장함수 이용

      import math
      math.lcm(x,y)