[Algorithm] Euclidean Algorithm in python

유클리드 호제법을 이용한  최소공배수(GCD)구하기

유클리드 원론에  기술되어있으며, 서로간의 값을 나눈다 하여 붙여진 호제법, 최대공약수(GCD : Greatest common divisor) 를 구하기 위한 인류 최초의 알고리즘이라 불리운다. 

두 양의 정수 a,b(b>a)에 대하여  b=aq+r,(0≤r<a)라 하면, a,b a,b의 최대공약수는 a,r a,r의 최대공약수와 같다. 즉, gcd(a,b)=gcd(a,r).

소인수 분해를 이용한 방법도 있지만 유클리드 호제법을 이용하면 훨씬 빠르게 구할 수 있다.

소인수 분해를 이용한 최대공약수 구하기

  2 | 1000, 300

  2 |   500, 150

  5 |    250, 75

  5 |      50, 15

            10, 3 

  5^2 x 2^2  = 25 x 4 = 100

유클리드 호제법을 이용한 최대공약수 구하기

1000 = 300 x 10 + 100

300 = 100 x 3

유클리드 호제법 계산량이 더 간결하다는 것을 확인 해 볼 수 있다.

이러한 이유로 다양한 알고리즘에도 활용된다. (RSA 키생성 알고리즘 등)

python을 통해 유클리드 호제법에 대한 구현 예제를 작성하였다.

euclide.py

import sys

def gcd(a, b) :
  print "%d = %d x %d + %d" % (a,b,a/b,a%b)
  if(a % b == 0) :
    print "GCD : %d" % b
    return
  else :
    gcd(b, (a%b))

if len(sys.argv) < 3 :
  print "Usage : python euclide.py \"INT\" \"INT\"";
  sys.exit(-1)
else :
  a = int(sys.argv[1])
  b = int(sys.argv[2])
  if a > b :
    gcd(a,b)
  else :
    gcd(b,a)

참조 URL : https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95