프론트엔드 센트럴파크 (☞ﾟヮﾟ)☞

유클리드 호재법 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 호재법이라는 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다. 이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다. 나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다. 이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다. GCD(a, b) = GCD(b, r) 유클리드 호제법 사용 // a를 b로 나눈 나머지가 0보다 클 때 까지 반복 static int gcd(int a, int b){ //..