티스토리 뷰

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

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


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

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

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



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


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



댓글