최대공약수

유클리드 호제법으로 표현되는 식

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.