1. 최대공약수

  • Greatest Common Divisor
  • 공약수는 정수 i의 약수이자 정수 j의 약수이다.
  • 최대공약수는 공약수 중 가장 큰 값이다.

2. 구현

2-1. 유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

다음은 유클리드 호제법을 이용하여 최대공약수를 구하는 자바 코드이다.

public class GreatestCommonDivisor {
  public static void main(String[] args) {
    int i = 663;
    int j = 2427;
 
    GreatestCommonDivisor gcd = new GreatestCommonDivisor();
 
    int result = 0;
 
    if (i > j)
      result = gcd.get(i, j);
    else
      result = gcd.get(j, i);
 
    System.out.println("gcd="+result);
  }
 
  int get(int i, int j) {
    if (j == 0)
      return i;
    else
      return get(j, i % j);
  }
}