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

1. 정의

- 두 수의 최대공약수를 구하는 알고리즘

 

2. 방법

- 2개의 자연수 a, b(a > b) 에 대해서  a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대공약수와 같음 

-> 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다.

3. 비교

유클리드 호제법이 아닌 다른 방법으로 코드를 작성한 후, 시간을 비교해보았습니다.

최대공약수 구하는 방법1

 

방법1: 결과값과 시간

유클리드 호제법

유클리드 호제법: 결과 값과 시간

2초 가량 차이가 난다. 

 

결론: 최대공약수를 구할 땐 유클리드 호제법을 이용하자