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.
No hay comentarios:
Publicar un comentario