GCD

유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘이다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) return b; a = b; b = r; }..