[알고리즘] 유클리드 호제법 (Euclidean Algorithm)

정수론

 

[알고리즘 소개]

두 자연수의 최대 공약수를 빠른 속도로 구하는 알고리즘.

 

 

[알고리즘 특징]

• 반복문을 사용하는 경우 $a \ge b$

[코딩 방법]

1. b == 0인 경우 return a
2. b != 0인 경우 return gcd(b, a % b)

[시간복잡도]

$O(logN)$

 

 

[공부용 링크]

coding-factory.tistory.com/599