CS/Algorithm & Data Structure
유클리드 호제법(최대공약수 재귀로 구하기)
Yeji Heo
2023. 2. 21. 02:52
두 자연수의 최대공약수를 구하는 대표적 알고리즘.
특징: 자연수 A,B에서 A%B=R일 때
A,B의 최대공약수 == B,R의 최대공약수
예를 들어 A: 192와 B: 162의 최대공약수를 구할 때(GCD(192,162))
Level | A | B |
1 | 192 | 162 |
2 | 162 | 30 |
3 | 30 | 12 |
4 | 12 | 6 |
즉, 192와162의 최대공약수는 12와 6의 최대공약수(즉, 6)과 동일하다.
따라서 재귀함수를 통해 R이 0이 아닌 동안 두 수를 나누도록 구현할 수 있다.
def gcd(a, b):
if a%b==0:
return b
return gcd(b, a%b)
print(gcd(192,162))