[알고리즘] 유클리드 호제법을 이용하여 최대 공약수를 구하는 알고리즘

유클리드 호제법을 이용하여 최대 공약수를 구하는 알고리즘

---

유클리드 호제법 예시

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

(위키백과 출처)

---

유클리드 호제법 알고리즘은 재귀함수를 사용하여 구현한다.

public class study01 {
    
    //최대공약수를 구하는 알고리즘
    static int gcd(int x, int y) {
        if(y==0) return x;
        else return gcd(y,x%y);
    }
    
    public static void main(String[] args) {
        Scanner stdInt = new Scanner(System.in);
        System.out.println("두개의 정수를 입력하세요.");
        int x=stdInt.nextInt();
        int y=stdInt.nextInt();
        System.out.println("최대 공약수는 "+gcd(x,y)+"입니다.");
        
    }
 
}​

 

실행 결과

Java 로 코딩하였습니다.