Euclidean Algorithm

유클리드 호제법

CRYPTOHACK의 MODULAR ARITHMETIC 1번째 문제(유클리드 호제법을 통해 두 수의 최대공약수를 구하는 문제)를 풀기 위해 유클리드 호제법을 코드로 구현해 보았다!

처음에는 나머지만 출력되게 해서 플래그를 구했지만 확실히 이해되게 구현해 보고 싶어서 식 전체를 반복문으로 출력하는 코드로 수정했다.

코드

n=66528
b=52920
a=0

for i in range(100):
    r = n % b
    if(r==0):
        print(n,'=',a,'*',b,'+',r)
        break
    else:
        a=int(n/b)
        print(n,'=',a,'*',b,'+',r)
        n=b
        b=r

출력값

66528 = 1 * 52920 + 13608
52920 = 3 * 13608 + 12096
13608 = 1 * 12096 + 1512
12096 = 1 * 1512 + 0

1번 문제를 푼 이후에 2, 3번 문제도 풀면서 코드 구현에 도전해 보았지만 완벽하게 이해가 되지 않아 블로그에 올릴 수 없습니다 ㅜㅜ 끝