파이썬 유클리드 알고리즘(Euclidean Algorithm) 구현 - 공부하는 도비

오늘은 간단한 코드 하나를 소개해볼까 합니다.

 

유클리드 알고리즘은 두 정수의 최대공약수를 쉽게 계산할 수 있도록 하는 것입니다.

(자세한 유클리드 알고리즘의 설명은 위키피디아를 참고해주세요.)

# Euclidean Algorithm

import sys

a, b = map(int, sys.stdin.readline().split())

print(" ")
q, r = 0, 0

while(True):
    if a < b : 
        a, b = b, a         # swap

    q = a // b
    r = a - (q*b)
    print(a ,'=', q, '*', b, '+', r)    

    if r == 0:
        print("\ngcd = ", b)
        if b == 1:
            print("relatively prime")
        break
    a = b
    b = r

 

 

유클리드 알고리즘을 간단하게 설명하자면, 

나머지가 0이 될때 까지 연산을 하다가, 나머지가 0이 되는 그 순간을 최대공약수라고 부르는 게 됩니다.

 

코드를 보면, 서로소라는 출력이 있는 것도 볼 수 있는데, 

서로소(relatively prime)라고 하는 건, 두 수의 최대공약수가 1인 경우를 뜻합니다.

예를 들어서,

13과 17은 서로소이므로, gcd가 1이고, relatively prime 이 출력되는 걸 확인할 수 있습니다.