[Algorithm] 유클리드 호제법(Euclidean algorithm)

✨ 유클리드 호제법(Euclidean algorithm)

유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

 

✨과정

1. a,b 두개의 자연수가 있다 (a>b)
2. a/b -> 나머지 r1
3. a/r1 -> 나머지 r2
4. 3번을 반복
5. a/r -> 나머지 0 일때 r은 a,b의 최대공약수다.

 

A,B=list(map(int,sys.stdin.readline().rstrip().split(" ")))
if (B>A):A,B=B,A
num=A
r=B
while True:
    r1=num%r
    if(r1==0): break
    num=r
    r=r1

print(r)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95