유클리드 호제법 | 7월 20일

유클리드 호제법

코딩으로 최대공약수를 구한다면 시간 복잡도를 줄이기 위해 유클리드 호제법을 사용한다.

사용방법

두 수중 큰수에서 작은수를 뺴서 작은수와 차가 같아지는 경우 그 수가 최대 공약수 이다.

예) 12, 30

    30 - 12 = 18
 => 18 - 12 = 6
 => 12 - 6  = 6
 최대 공약수는 6이다

💡 유클리드 호제법을 이해하기 위해서는 MOD연산에 대해 알고 있어야 한다.
-> MOD연산이란? 두 값을 나눈 나머지를 구하는 연산!

---

프로그램

반복문(while)을 이용한 방법

⑴ 두 수를 입력 받을 변수int를 선언.
⑵ GCD변수를 출력하기 위해서 함수를 사용한다.
⑶ 반복문을 이용하여 계산한다.
⑷ bignumber를 return함으로써 결과를 도출한다.