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

최대 공약수를 구하는 대표적인 유클리드 알고리즘에 대해 말해보려 한다. 최대 공약수는 수학적으로 다음과 같이 정의 할 수 있다. 이 값을 구하기 위해서 유클리드 알고리즘이 적용되는 방법은 예제를 보면 어떤 구조인지는 대략 감이 잡힌다. 12와 128의 최대 공약수를 구할 때 큰 수에서 작은수로 나눈 나머지를 구하고 원래 작은 수가 그 나머지보다 작아지면 또 반대로 나머지를 구하며 반복하다 나머지가 0이 나오면 바로 그 전의 값이 최대 공약수가 되는 것이다. 유클리드 알고리즘 증명 사실 알고리즘으로 보면 엄청 간단하다.. 알고리즘이 코드와 별반 다른 것이 없을 정도로 간단하지만 Java로 최대 공약수 구하는 함수는 이렇게 쓸 수 있다. private static long gcd(long a, long b)..
거인의 어깨위에 서려는 2015. 11. 16. 21:55
1