viernes, 13 de septiembre de 2013

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.

No hay comentarios:

Publicar un comentario