유클리드 호제법으로 표현되는 식
a = b * q + r
변수를 보고 이해할 수 있게 변형
big = small * div + residue
big=int(input("big = "))
small=int(input("small = "))
def gcd(big,small):
# 올바른 순서 맞추자
if big < small:
temp = big
big = small
small = temp
# 최대공약수 구하자
print(" big = small * div + residue")
while small != 0:
residue = big % small
# %숫자 d에서 숫자는 자릿수를 의미합니다
print("%4d = %5d * %3d + %7d" %(big, small, big/small, residue))
big = small
small = residue
return big
print("The gcd is %d." %gcd(big,small))
코드 돌리기
80과 36의 최대공약수 구하자
big = 80
small = 36
big = small * div + residue
80 = 36 * 2 + 8
36 = 8 * 4 + 4
8 = 4 * 2 + 0
The gcd is 4.
100과 28의 최대공약수 구하자
big = 100
small = 28
big = small * div + residue
100 = 28 * 3 + 16
28 = 16 * 1 + 12
16 = 12 * 1 + 4
12 = 4 * 3 + 0
The gcd is 4.