Generando números primos.
Los números primos son el misterio de las matemáticas. Son esos números que solo se pueden dividir por 1 y por ellos mismo. En general no tenian mucha utilidad hasta que comenzaron a usarse para criptografía. Pero siempre han despertado la curiosidad de los aficionados a las matemáicas en razón a que su distribución en la recta de números enteros no parece tener un patrón, parecerían puestos al azar.
Doscientos años antes de Cristo el matemático griego Eratóstenes de Cirene se entretenia calculando números primos. Creó una técnica para encontrar los números primos en un rango de números, a esto se le llama la criba de Eratóstenes. El método es sencillo y perfecto para comenzar a jugar con Python. Imagine que tiene una lista de números del 1 al 100 y desea conocer cuales de ellos son primos. El método consiste en suponer que todos son primos y empezar a descartar, al finalizar, los no descartados, serán los primos.
Apliquemos el método describiéndolo de forma narrativa y luego haremos un programa para cálcular los números primos que se encuetran en digamos un rango entre 1 y mil millones usando Python y nuestro modesto portatil.
El método comienza con la certeza que el 1 y el 2 son primos. En principio todos los números están marcados como candidatos a primos pero no tenemos dudas que estos dos lo son. Ubicados en el número 2, multiplicamos a si mismo y a los números que le siguen por 2 hasta llegar a nuestro límite (100 para nuestro ejemplo inicial) el resultado lo desmarcamos, ya no será candidato a número primo. De tal forma que quedan desmarcados el 4,6,8,10,12,14,16,… etc, todos los pares. Pasamos al siguiente número no desmarcado, el 3 y multiplicamos los números que le siguen por 3, el resultado lo desmarcamos, quedando descartados todos los números múltiplos de 3: 9,12 (ya habia sido desmarcado), 15,18,21…. etc, el siguiente número no desmarcado es el 5, al aplicar el método se desmarcarán todos los múltiplos de 5 (los terminados en 0 o en 5: 10,15,20,25,30,…etc.) el método continua y no es necesario llegar a 100 basta con llegar al número cuyo cuadrado sea mayor que el límite, para nuestro ejemplo el límite es 100 y dado que 10 al cuadrado da 100. Al llegar a 10 ya habremos desmarcado todos los necesarios, los que quedan marcados son los números primos de 1 a 100.
Ahora llevemos el método a un programa en Python. Se deberá definir un límite del rango a examinar, a esa variable la llamaremos limite. Se puede ver que se requerirán dos bucles uno que recorra los números del 2 hasta la raiz cuadrada del límite y otro desde el número que estamos examinando hasta el límite. Además Python permite definir rangos de forma muy sencilla: range(1,limite). Bueno vamos en orden:
1. Librerias. Importamos las librerias math y time. La primera porque requerimos hacer operaciones matemáticas y la segunda por que calcularemos el tiempo que tarda nuestro programa en generar los números en un rango dado.
import math, time
2. Parámetros. Definimos las varibales que usaremos: limite: para el rango de números, el nombre del archivo donde guardaremos los primos encontrados y el número hasta el cual recorreremos uno de los bucles (la raiz cuadrada del límite).
import math, time
limite = 1000000
cuadrado_limite = int( limite**(1/2) ) # Lo convertimos a entero para evitar problemas en los bucles
nombre_archivo = 'primos_hasta_'+str(limite)+'.txt'
inicio = time.time() # Tiempo en el cual comienza la ejecución
3. Crear la criba. Crearemos una lista del tamaño que queramos. Será nuestra criba. Esta lista estará llena de unos (1s) y la posición en la lista dirá a qué número nos referimos. De tal forma que todas las posiciones inicialmente tendrán un 1, indicando que son candidatos a primos. En la medida que descartemos números, el contenido de la posición respectiva la reemplazaremos por un cero (0).
# Crea lista de unos
criba = list((1,1,1)) # Inicializa la lista con los unos correspondientes a la posición 0, 1 y 2
for i in range(0, limite - 1 ):
criba.append(1)4. Recorremos la criba. Con un bucle for recorremos desde el número 2 hasta la raiz cuadrada del límite. Dentro de este bucle creamos otro que recorre desde el número en que vamos hasta un número que al multiplicarlo por el número en que vamos no supere el límite.
Multiplicamos estos dos índices y en la posición de la lista correspondiente al resultado de la multiplicación cambiamos el número (inicialmente era un 1) por un cero. Descartándolo como número primo.
for index in range(2, cuadrado_limite):
if (criba[index] == 1 )
for index2 in range(index,math.floor(len(criba)/index)):
criba[index*index2] = 05. Guardamos los resultados. Ya tenemos una lista de python llamada criba que contiene ceros y unos (podriamos hacerlo con True y False, probablemente sería un uso más eficiente de la memoria). La posición donde encontremos un 1 será un número primo. Ahora guardemos los resultados en un archivo de texto. Pero antes imprimamos en patalla el tiempo de finalización y el transcurrido (en segundos):
#Resultados
print('Fin: ',time.time())
print('Tiempo transcurrido: ',time.time() - inicio)Por supuesto un equipo con mejor desempeño de procesador será más rápido y uno con suficiente memoria RAM permitirá hacer cribas muy grandes.
Para imprimir los resultados sólo debemos recorrer la lista llamada criba. Lo hacemos con un ciclo for con dos indices, el primero captura del consecutivo del for y el segundo el valor de la lista:
f = open(nombre_archivo, "w")
for i,x in enumerate(criba):
if x ==1:
f.write(str(i)+'\n')
f.close()Ahora todo junto
El código completo sería el siguiente:
#Generación de números primos con el método de Criba de Eratóstenes
import math, time
limite = 1000000000
nombre_archivo = 'primos_hasta_'+str(limite)+'.txt'
inicio = time.time()
print('Inicio: ',inicio)
cuadrado_limite = int( limite**(1/2) )
# Crea lista de unos
criba = list((1,1,1))
for i in range(0, limite - 1):
criba.append(1)
#Recorre lista
for index in range(2, cuadrado_limite):
for index2 in range(index,math.floor(len(criba)/index)):
criba[index*index2] = 0
#Resultados
print('Fin: ',time.time())
print('Tiempo transcurrido: ',time.time() - inicio)
f = open(nombre_archivo, "w")
for i,x in enumerate(criba):
if x ==1:
f.write(str(i)+'\n')
f.close()Generando los números primos hasta 1000 millones mi portatil con 16 Gigas de RAM y procesador Intel Core i7 de séptima generación (viejito) se demoró 40 minutos (2.397 segundos).
Aunque grabando el archivo se demoró otros 10 minutos. Generó un archivo de texto de 539.85 megabytes, que dejo a continuación, por que será útil para seguir jugando con primos en otras entradas. Está en formato texto con extensión htm comprimido en zip: MUCHOS NÚMEROS PRIMOS
0 Comentarios