Algoritmo para calcular el máximo común divisor

dados dos números, obtener el máximo número que divida a ambos.
Para ello, lo primero que había que hacer era descomponer cada número en factores primos. Por ejemplo, para calcular el mcd (máximo común divisor) de 756 y 1617:

756 = 7 * 3^3 * 2^2
1617 = 11 * 7^2 * 3

A continuación tomamos los factores comunes elevemos al menos exponente y ese es el mcd; en nuestro ejemplo:

mcd(756,1617) = 7 * 3 = 21

Hacer esto es relativamente sencillo, ahora bien, programarlo ya es otra cosa bien distinta. Lo más complicado sería implementar una función que descomponga un número en sus factores primos.
Se podría hacer, si bien existe un método bastante más sencillo: utilizando el algoritmo de Euclides. ¿En qué consiste? De forma resumida, el pseudocódigo para la función que calcula el mcd quedaría:

function mcd(a, b) {
if (a > b) {
return mcd(a-b, b);
} else if (b > a) {
return mcd(a, b-a);
} else { // a == b
return a;
}
}

Aplicándolo a nuestro ejemplo:

mcd(756,1617) = mcd(756,861) = mcd(756,105) = mcd(651,105) = mcd(546,105) = mcd(441,105) = mcd(336,105) = mcd(231,105) = mcd(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21

Por supuesto, este algoritmo es susceptible de ciertas mejoras. Por ejemplo, multiplicar y dividir por 2 es algo sencillo utilizando las operaciones de bits: al desplazar un bit a la izquierda estamos multiplicando por 2 y al desplazarlo a la derecha estamos dividiendo por 2. De esta forma, podríamos ahorrarnos algunos pasos en el ejemplo anterior:

function mcd_mejorado(x, y) {
var mayor = max(x,y);
var menor = min(x,y);
if (mayor > (menor << 1)) {
return mcd_mejorado(mayor - (menor << 1), menor);
} else {
return mcd(mayor,menor); //llamada a la funcion anterior
}
}

Volviendo a nuestro ejemplo:

mcd_mejorado(1617,756) = mcd_mejorado(756,105) = mcd_mejorado(546,105) = mcd_mejorado(336,105) = mcd_mejorado(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21

Algoritmo para calcular números primos

Por qué cambiar de algoritmo para calcular los números primos? Pues porque el que hay ahora 2 E NP -1 (2 elevado a un numero primo, al resultado se le resta 1) el resultado que da no se sabe si es primo y hay que comprobarlo, con mi algoritmo no hay que preocuparse de si es o no primo porque (al menos teoricamente) ya he probado que siempre da números primos.

La lista tendrá este formato:

ejemplo de algoritmo matemático.número primo

ejemplo de algoritmo

Algoritmo

Es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quienes deban realizar dicha actividad. En la vida cotidiana se emplean muchos algoritmos para resolver problemas. Algunos ejemplos son los manuales de usuario, que mustra algoritmos para usar un aparato o las instrucciones que recibe un trabajador se su trabajador.