Máximo Común Divisor

En esta entrada vamos a ver un sencillo algoritmo para el cálculo del máximo común divisor de dos números dados. Recordemos que el máximo común divisor de dos números enteros positivos a y b, escrito como MCD(a, b), es el mayor de los divisores comunes de a y de b, es decir, el mayor de aquellos números que dividen a la vez a ambos. Por ejemplo MCD(6, 4) = 2, MCD(9, 6) = 3, y MCD(11, 9) = 1. El cálculo del máximo común divisor resulta muy útil a la hora de simplificar facciones, por ejemplo la fracción 60/18 podríamos simplificarla como 60/18 = (6*10) / (6*3) = 10 / 3.

En el siguiente algoritmo podemos encontrar un método para el cálculo del máximo común divisor. El algoritmo recibe como parámetros de entrada dos números, a y b, y como resultado nos muestra en pantalla el MCD(a, b). Para ello, el algoritmo se basa en un procedimiento muy simple: primero calcula cual es el menor de los números a y b, a continuación recorre todos los números que van desde 1 hasta el menor de a y b, y para cada uno de ellos comprueba si divide a la vez a ambos, utilizando la ya conocida función módulo(), que recordemos nos devuelve el resto de la división entera entre dos números x e y. Al final del bucle repetir, tendremos en la variable mcd el mayor de los números que han dividido a la vez a a y b, es decir, su máximo común divisor.

leer(a)
leer(b)
min := mínimo(a, b);
repetir desde x := 1 hasta x := min
    si (módulo(a, x) = 0) y 
           (módulo(b, x) = 0) entonces
        mcd := x
    fin si
fin repetir
escribir(mcd)

Existen muchas formas de mejorar el algoritmo anterior. Por ejemplo, no haría falta comprobar cuales son los divisores de a y b desde 1 hasta mínimo de a y b, bastaría con comprobar desde 1 hasta la raiz cuadrada del mínimo (¿podría explicar el lector por qué?). Otra manera más refinada de calcular el MCD sería mediante la factorización de los números a y b, aunque este procedimiento no es necesariamente más eficiente.

En la siguiente entrada de este blog veremos una forma muy sencilla, y muy eficiente, de calcular el máximo común divisor de dos números, el conocido como Algoritmo de Euclides.

Números Primos

En una entrada anterior de este blog vimos un algoritmo que calculaba números factoriales. En esta entrada vamos a ver otro ejemplo de algoritmo, que determina si un número es primo o no. Este segundo algoritmo nos permitirá introducir nuevos conceptos sobre programación.

Recordemos que un número primo es aquel que sólo es divisible por sí mismo y por la unidad; y recordemos también que decimos que un numero es divisible por otro cuando el resto de la división entera es 0. Veamos algunos ejemplos. El 4 es divisible por 2 porque al hacer la división de 4 entre 2 nos da como resultado 2 y de resto 0. De igual manera decimos que 5 no es divisible por 2, ya que la división nos da 2 junto con un resto de 1. Por otro lado, el número 4, al ser divisible por 2, no es un número primo. En cambio, el número 5, que no es divisible ni por 2, ni por 3, ni por 4, es un número primo (sólo es divisible por sí mismo y la unidad).

A modo de ejemplo, los diez primeros números primos serían (no, el número 1 no es un número primo, por definición):

2, 3, 5, 7, 11, 13, 17, 19, 23, y 29

Los números primos juegan un papel muy importante, no sólo en matemáticas, sino también en informática. En matemáticas, existen libros enteros dedicados a los números primos: historia, propiedades, aplicaciones, curiosidades, etc. Y en informática, los números primos son utilizados por los algoritmos de cifrado basados en claves públicas, que son básicos en áreas como la telefonía móvil o las transacciones bancarias.

Ahora, básicamente, lo que queremos es escribir un sencillo algoritmo que, dado un número, nos diga si es primo o no es primo. Antes de seguir leyendo, es conveniente que el lector le eche un vistazo rápido al siguiente algoritmo, a ver qué puede entender. Si no lo entiende en su totalidad, no se preocupe, que para eso estamos aquí, para explicar las cosas en detalle. Este nuevo algoritmo es muy parecido al algoritmo para el cálculo del factorial de un número que ya hemos visto. Recordemos que para calcular el factorial de un número n lo que hacíamos es utilizar un bucle que recorriese todos los valores desde 1 hasta n multiplicándolos. En este nuevo caso lo que necesitamos es un bucle que recorra todos los valores desde 2 hasta n-1, y para cada uno de ellos compruebe si dividen a n.

leer(n)
primo := CIERTO

repetir desde i:=2 hasta i:=n-1
    si modulo(n, i) = 0 entonces
        primo := FALSO
    fin si
fin repetir

si primo = CIERTO entonces
    escribir(“¡Es primo!”)
fin si

si primo = FALSO entonces
    escribir(“No es primo”)
fin si

Para saber si un número divide a n tendríamos que ver el resto de la división de n entre ese número. Sin embargo, esta división, que a simple vista no tiene mayor complicación, puede llegar a convertirse en un problema. Si le decimos a un ordenador que calcule 5/2 nos va a dar como resultado 2.5, que no es lo que queremos, ya que lo que queremos saber es el resto de la división sin recurrir a decimales. La mayoría de los ordenadores proporcionan algún mecanismo, o bien para conocer el cociente de las divisiones enteras, o bien para conocer directamente el resto de dichas divisiones. En nuestro caso, y por no complicar innecesariamente las cosas, supondremos que nuestro ordenador tiene un mecanismo llamado módulo(x, y) que nos devuelve el resto de la división enterea de x por y. Así por ejemplo:

módulo(4, 2) = 0
módulo(5, 2) = 1

En realidad el algoritmo descrito es muy simple y puede ser mejorado enormemente, vamos a ver cómo.

La primera mejora es bastante obvia, una vez que hemos encontrado un número que divide a n ya tenemos la seguridad de que n no es primo, y por tanto, no tiene sentido que sigamos calculando si es divisible por otros números. En este caso, simplemente lo que tendríamos que hacer es terminar el bucle tan pronto encontremos el primer divisor de n, y así no le hacemos perder el tiempo a nuestro usuario. La segunda mejora, quizás no tan obvia, consiste en lugar de repetir el bucle desde 2 hasta n-1, es mejor, y suficiente, con hacerlo desde 2 hasta la raíz cuadrada de n. Dejo al lector como ejercicio que explique por qué es esto así.

leer(n)
primo := CIERTO

repetir desde i:=2 hasta i:= raiz(n)
    si módulo(n, i) = 0 entonces
        primo := FALSO
        salir
    fin si
fin repetir

si primo = CIERTO entonces
    escribir(“¡Es primo!”)
si no
    escribir(“No es primo”)
fin si

A aquellos lectores con un poco más de experiencia, les propongo como ejercicio, que extiendan el algoritmo para que en lugar de decirnos si n es un número primo, lo que haga es mostrarnos todos los números primos existentes menores que n. Lo que tendría que hacer el lector es utilizar dos bucles anidados, es decir, uno dentro de otro: un primer bucle que recorra todos los números desde 1 hasta n-1, y un segundo bucle que compruebe si dichos números son, o no son, primos.

Números Factoriales

A veces, cuando voy al cine con mi mujer y mis dos hijos, tenemos ciertas dificultades para decidir cual es la mejor manera de sentarnos. Podríamos simplemente sentar a los niños en las butacas centrales, y nosotros dos en las laterales, pero si hacemos esto, seguramente acaben peleándose en mitad de la película. Quizás lo mejor sea sentarlos lo más alejados posible, cada uno en una butaca lateral, y mi mujer y yo en las centrales, pero claro, existe el riesgo de que la pequeña acabe molestando a otros espectadores. O quizás podríamos optar por sentar al mayor en un extremo, a su lado mi mujer, después la pequeña, y finalmente yo. Pero no, esto tampoco vale, el mayor acabaría protestando porque la pequeña está entre papá y mamá, y él no. En fin, un problema, que al día de hoy, sigue pendiente de solución.

Al hilo de esto me gustaría plantear al lector otro problema, mucho más fácil de resolver, que consiste en contar de cuántas maneras posibles se pueden sentar cuatro personas en cuatro butacas de cine (lo que en matemáticas se conoce como el nombre de permutaciones). Centrémonos primero en la primera butaca. ¿Quiénes nos podríamos sentar en ella? Pues cualquiera de nosotros, es decir, cuatro. Supongamos ahora que alguien (da igual quién porque ya hemos tenido en cuenta que se puede sentar cualquiera de nosotros), ya se ha sentado en la butaca uno. ¿Cuantos de nosotros se pueden sentar en la butaca dos? Pues cualquiera de los tres que quedamos. Igualmente, cuando alguien se sienta en la segunda butaca, en la tercera quedan dos para sentarse. Y finalmente, cuando alguien se sienta en la tercera butaca, sólo queda uno, que ha de sentarse necesariamente en la cuarta butaca. En resumen, nos podemos sentar de 4*3*2*1=24 maneras diferentes. O dicho de otra forma, nos podemos sentar de 4! formas distintas. Lo que me da pie a introducir el concepto de factorial de un número, que es a lo que vamos.

El factorial de un número entero positivo n, escrito como n!, es el producto de todos los números enteros positivos menores o iguales que n. Por ejemplo:

5!=1*2*3*4*5=120

El concepto de factorial es muy útil en matemáticas, entre otras cosas, como hemos visto, para el cálculo de permutaciones. También son muy útiles para pasar el rato en el cine mientras empieza la película. Pero en realidad lo que ahora nos interesa es que los factoriales nos van a permitir introducir nuestro primer algoritmo.

leer(n)
x := 1
repetir desde i:=1 hasta i:=n
    x := x*i
fin repetir
escribir(x)

Para finalizar, a aquellos lectores que se animen a escribir este algoritmo en un ordenador real, les recomiendo que tengan un poco de cuidado con el valor que escogen para n. Hay que tener en cuenta que el cálculo de factoriales pueden dar como resultado números muy grandes, incluso para valores de n pequeños. Por ejemplo, el factorial de 10 es 3.628.880, y el factorial de 20 nos da ya el increíble valor de 2.432.902.008.176.640.000. Aquellos lectores que no les apetezca programar un algoritmo tan simple, también pueden divertirse hallando factoriales con una calculadora. La mayoría de las calculadoras de sobremesa son capaces de llegar hasta 69!. Esto es así porque las calculadoras nos muestran el resultado utilizando notación científica con dos dígitos para el exponente, y 70! requeriría ya de un exponente de tres dígitos.