/**
* Calcola il massimo comun divisore (MCD) fra due
* numeri interi positivi m e n
*
* @author Adriano Luchetta
* @version 16-Ott-2005
*/

/* Algoritmo di Euclide
   Siano m e n due numeri interi positivi con m > n.

   1. sia i = m e j = n
   1. finche' i % j e' diverso da zero ripetere il passo 2
      2. i = j , j = i precedente % j
   3. MCD(m,n) = j
*/

import java.util.Scanner;

public class MCD
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);
         
      System.out.println("***CALCOLO DEL MCD(m,n)***\n");

      System.out.print("m e n?: ");
      int m = in.nextInt();
      int n = in.nextInt();

      // verifica che i numeri siano positivi
      if (m <= 0 || n <= 0)
      {
         if (m <= 0)
            System.out.println("m = " + m + ": ingresso non ammesso");
         if (n <= 0)
            System.out.println("n = " + n + ": ingresso non ammesso");

         return;
      }

      // Ordinamento
      int i = m;
      int j = n;
      if (m > n) // pongo i > j
      {
         i = n;
         j = m;
      }

      // Algoritmo di Euclide
      int tmpInt;
      while ((tmpInt = i % j) != 0)
      {
         i = j;
         j = tmpInt;
      }
      
      // Stampa su output standard
      System.out.println("MCD(" + m + "," +	n + ") = " + j);
   }
}