[JAVA] 유클리드 호제법_최소공배수, 최대공약수 구하기

유클리드 호제법 이란? 유클리드 알고리즘 (Euclidean algorithm) 은 2개의 자연수의 최대공약수(GCD) 를 구하는 알고리즘 이다. 비교대상인 두 개의 자연수 a와 b에서 (이때, a>b) a를 b로 나눈 나머지를 r 이라고 했을때 GCD(a, b) = GCD(b, r) 이며, "r이 0이면 그때 b가 최대공약수이다." 라는 원리를 활용한 알고리즘 이다. 만약 r이 0이 아니라면 a에 b값을 다시 넣고, r을 b에 대입 한 후 다시 반복한다. 1) 반복문을 이용해서 최대공약수 구하기 int gcd(int a, int b) { //최대공약수 while(b!=0) { int r=a%b; a=b; b=r; } return a; } 2) 재귀함수를 이용해서 최대공약수 구하기 //재귀함수 사용 - ..