최대공약수 알고리즘 + 코드

최대 공약수를 구하는 대표적인 유클리드 알고리즘에 대해 말해보려 한다.

최대 공약수는 수학적으로 다음과 같이 정의 할 수 있다.

이 값을 구하기 위해서 유클리드 알고리즘이 적용되는 방법은 예제를 보면 어떤 구조인지는 대략 감이 잡힌다.

12와 128의 최대 공약수를 구할 때 큰 수에서 작은수로 나눈 나머지를 구하고

원래 작은 수가 그 나머지보다 작아지면 또 반대로 나머지를 구하며 반복하다 나머지가 0이 나오면 바로 그 전의 값이 최대 공약수가 되는 것이다.

유클리드 알고리즘 증명

사실 알고리즘으로 보면 엄청 간단하다..

알고리즘이 코드와 별반 다른 것이 없을 정도로 간단하지만 Java로 최대 공약수 구하는 함수는 이렇게 쓸 수 있다.

private static long gcd(long a, long b){ if(b==0) return a; else return gcd(b, a%b); } //이건 알고리즘을 보지 않고 내가 짠 것 private static long gcd(long l, long min) { long tmp = l/min; l -= tmp*min; if(min%l == 0) return l; else return gcd(min,l); }