// 사용자가 입력하는 두 수의 최대공약수 구하기 

import java.util.Scanner;

public class GCD {
	public static void main (String[] args) {
		Scanner sin = new Scanner(System.in);
		System.out.print("임의의 두 정수를 입력하시오>> ");
		int num1 = sin.nextInt();
		int num2 = sin.nextInt();
		int divisor, remainder;
		if (num1 < num2) { // num1이 큰 수, num2가 작은 수가 되게 한다.
			int tmp = num2;
			num2 = num1;
			num1 = tmp;
		}
		divisor= num2; // 작은 수를 나눗수로 한다.
		while ((remainder = num1 % divisor) != 0) { //0으로 나누어 떨어지면 나눗수가 최대 공약수
			num1 = divisor; // 나눗수를 나뉨수로 한다. 
			divisor = remainder; // 나머지를 나눗수로 한다.
		}
		System.out.println("최대 공약수는 " + divisor);
	}
}