GCD.java

import java.util.*;

public class GCD {
  /* NAIVE GCD ALGO
   private static int gcd_naive(int a, int b) {
    int current_gcd = 1;
    for(int d = 2; d <= a && d <= b; ++d) {
      if (a % d == 0 && b % d == 0) {
        if (d > current_gcd) {
          current_gcd = d;
        }
      }
    }

    return current_gcd;
  }
  */
  public static int euclid_gcd(int a, int b){
	  if(b==0){
		  return a;
		  }
	  int x = a%b;
	  return euclid_gcd(b,x);
		  
	  }

  public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    int a = scanner.nextInt();
    int b = scanner.nextInt();

    System.out.println(euclid_gcd(a, b));
  }
}