Uno de los algoritmos más antiguos es la del algoritmo de Euclides, Se llama así en honor del matemático griego Euclides, quien lo describió en los libros VII y X. Este algoritmo nos permite hallar el máximo común divisor de dos números (Por lo general positivos), Euclides lo plantea originalmente como una serie de restas sucesivas, El proceso consiste en trabajar con dos numero enteros positivos a y b, en donde se resta el mayor “a” con el menor “b” hasta que ambos valores sean iguales ( a = b ). Por ejemplo:

   A        B
3768 - 1727 = 2041 //como 2041 es mayor que el valor de "b" entonces "a" es igual a 2014
2041 - 1727 = 314// como 314 es menor que el valor que "b" entonces "a" es igual a 1727
1727 - 314   = 1413
1413 - 314   = 1099
1099 - 314   = 785
785   - 314   = 471
471   - 314   = 157
314   - 157   = 157
157   - 157   = 0 //como los 2 resultados son iguales el MCD es 157

En el siguiente código es el algoritmo de Euclides basada en la versión original de las restas sucesivas realizado en java:

int MCD_Euclides(int a, int b){
  while(a != b){
     if(a > b){
        a = a - b;
     }else{
        b = b - a;
     }
  }
  return a;
}


La versión original del algoritmo utiliza las restas sucesivas, pero esto llega a ser menos eficiente, es por ello que existe otra versión, llamada la división euclidiana que reduce los pasos de intercambios entre los dos valores en un solo paso con el cálculo del resto (b = a mod b), de este modo resulta más eficiente.

A continuación el algoritmo con la versión mas optimizada realizado en java:

int MCD_Euclides(int a, int b){
    while(b != 0){
         int t = b;
         b = a % b;
         a = t;
    }
    return a;
}