유클리드 호제법: 최대공약수 알고리즘(Java, Python)

두 자연수의 최대공약수를 구하는 알고리즘이다. 재귀함수를 사용한다.

# 유클리드 호제법 A, B(자연수, A>B) 이고 A%B=R 일 때, gcd(A,B) = gcd(B,R)

 

#Java

public class gcd {
 
    public static int gcd(int a, int b) {
        if(a % b == 0)
          return b;
        else
          return gcd(b, a % b);
    }    
    
    public static void main(String[] args) {
        int result = 0; 
        result = gcd(192,162);
        
        System.out.println(result);
    }
 
}

#Python

def gcd(a, b):
  if a % b == 0:
     return b
  else:
     return gcd(b, a % b)
 
print (gcd(192,162))