최대 공약수

알고리듬 - 최대 공약수 & 최소 공배수 구하기(유클리드 호제법)

최대 공약수(GCD: Greatest Common Divisor)와 최소 공배수(LCM: Lowest Common Multiple) 를 구하는 방법에 대해 알아보자. 유클리드 호제법 유클리드 호제법(Euclidean-Algorithm)은 주어진 두 값의 최대 공약수를 구하는 알고리듬이다. 계산은 MOD 연산(%)을 활용한다. 진행 과정은 아래와 같다. 1. 주어진 두 값 중 큰 값을 작은 값으로 MOD 연산한다. 2. 앞의 과정에서 작은 값을 MOD 연산의 결과로 MOD 연산한다. 3. 결과가 0이 나오면 종료한다. 아래는 120과 34의 최대 공약수를 구한 예이다. 구현 내용이 어렵지 않아 바로 구현해 보았다. 전체 코드 package practice; public class GCD { public s..