최대 공약수 구하기 (GCD / the greatest common divisor / Euclid 알고리즘 / Java)

Euclid 알고리즘을 사용하여 최대 공약수 구하기 

class Euclid{
 
    // division-based version
    public int getGCD1(int num1, int num2) {
        if(num1 * num2 < 0){
            return -1;
        } 
        while(num2 != 0){
               int temp = num2; 
               num2 = num1 % num2 ; 
               num1 = temp; 
        }
        return num1;
    }
  
    // subtraction-based version
    public int getGCD2(int num1, int num2) {
        if(num1 * num2 < 0){
            return -1;
        } 
        while(num1 != num2){
            if(num1 > num2) {
                  num1 = num1 - num2;
              } else {
                  num2 = num2 - num1;
              }
        } 
        return num1;
    }
  
    // recursive version
      public int getGCD3(int num1, int num2) {
        if(num1 * num2 < 0){
            return -1;
        } 
        if(num2 == 0){
            return num1;
        } else {
            return getGCD3(num2, num1 % num2);
        }
      }
  
    // print  
    public static void main(String[] args) {
        Euclid euclid = new Euclid();
        System.out.println("최대 공약수: " + euclid.getGCD1(96,360));
        System.out.println("최대 공약수: " + euclid.getGCD2(360,96));
        System.out.println("최대 공약수: " + euclid.getGCD3(360,96));
        System.out.println("최대 공약수: " + euclid.getGCD3(-360,96));
        System.out.println("입력값이 0보다 큰 정수가 아닐 경우 -1 반환");
  }
}

시간 복잡도 O( log2(min(a, b)))

입력된 2개의 정수의 비트수를 n이라고 하면, 유클리드 알고리즘은 Θ(n) 회의 나눗셈으로 최대공약수를 구할 수 있다.