// ユークリッドの互助法での最大公約数の計算
import java.io.*;
import java.lang.*;

public class Euclidean {
  public static void main(String[] args) {
    int num1, num2, big, small, remain;
    String str1, str2;

    try {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      System.out.println("2つの数の最大公約数を計算します。");
      // 最大公約数を計算する 2 つの数を入力尾
      System.out.println("1つ目の数を入力してください。");
      str1 = br.readLine();
      num1 = Integer.parseInt(str1);
      System.out.println("2つ目の数を入力してください。");
      str2 = br.readLine();
      num2 = Integer.parseInt(str2);

      // 入力された数は、どちらが大きくてどちらが小さいかわからないので、それを
      // 判定し、大きい数を big、小さい数を small に代入
      if (num1 < num2) {
        small = num1;
        big = num2;
      } else {
        big = num1;
        small = num2;
      }
      
      remain = big % small;  // 2 つの数のうち、大きい数を小さい数で割り算し、余りを計算
      while (remain != 0) {  // 余りが 0 でなければ、割り算をした小さい数を大きい数とし、余りを小さいすうとしてまた割り算(これを余りが 0 になるまで繰り返す)
        big = small;
        small = remain;
        remain = big % small;
      }
      // 余りが 0 になったとき、最後の割り算をしたときの小さい数(割った数)が最大公約数(割った数は small なので、small を出力)
      System.out.println(num1 + "と" + num2 + "の最大公約数は" + small);
    }
    catch(IOException e) {
    }
  }
}