Calcular números primos con Python

Como todos sabemos, los números primos son aquellos números especiales por ser sólo divisibles por uno y por sí mismos. Números como 2, 3, 5, 7, 11, 13…y de ahí hasta el infinito, o eso se cree. Hay muchas teorías alrededor de los números primos, como la Conjetura de Goldbach, que dice que todos los números pares mayores de 2 son el resultado de la suma de dos números primos (y todavía no se ha demostrado ni desmentido), e incluso juegan un papel importantísimo en la criptografía, como cada vez que compramos on-line con nuestra tarjeta de crédito.

Pero hoy no vamos a hablar de números primos y sus aplicaciones. Vamos a hablar de cómo conseguir números primos con un script de Python. ¡Así que empecemos!

Script calculador de números primos

Para empezar, debemos tener en cuenta la definición de número primo: ‘Número divisible únicamente por uno y por si mismo’. Vale, la cosa va de divisiones. Si pensamos un poco, nos daremos cuenta de que un divisor es aquel número (d) contenido en otro (dividendo, D) un número exacto de veces (cociente, q). ¡Pero no se ha hablado de resto en ningún momento! Es decir, que el resto de dividir D/d = q, es igual a 0. Por tanto ya tenemos un cacho de código listo:

if D%d != 0:
    #d no es divisor de D, por lo que D puede ser primo
else:
    #d es divisor de D, por lo que D no puede ser primo
    isPrimo = False

Vale, vamos avanzando. En realidad, para saber si un número (x) es primo, tenemos que probar que todos los números enteros mayores que uno y menores que el propio número. Por tanto, ya tenemos otro cacho que añadir:

x = 73 #Número que queremos ver si es primo
for num in range(1, x):
    if x%num != 0:
        num no es divisor de x, x puede ser primo
    else:
        num es divisor de x, x no es primo

Una vez sepamos si nuestro número es primo o no, querremos probar con más números. ¿Cómo hacemos eso?¡Añadamos más código!

nmax = 1000 #Número máximo hasta el que queremos buscar primos
#Nota: empezamos en 3 porque 2 no tiene más posibles divisores que 1 y 2.
for x in range(3, nmax): 
   for num in range(1, x):
       if x%num != 0:
           num no es divisor de x, x puede ser primo
       else:
           num es divisor de x, x no es primo

Bueno, ahora hay que hacer que funciones. ¿Cómo? Tenemos que descartar los números que tengan más divisores que ellos mismos y que uno, porque no son números primos, y los números primos ¡tenemos que almacenarlos! Ahí va la última actualización de código:

primos = [2]
nmax = 1000
for x in range(3, nmax):
    for i in range(2, x):
        if x%i != 0:
            #i no es divisor de x, x puede ser primo
            continue
        else:
            #i es divisor de x, x no es primo
            break #No es necesario buscar más divisores
    else:
        #El bucle for ha terminado con normalidad
        #El número que estábamos comprobando es primo
        print '%d es primo'%x
        primos.append(x)
F = open('numerosprimos.txt', 'w')
for data in primos:
    F.write('%d\n'%data)

Y ya tendríamos nuestro código listo. Para acabar, un ejemplo de la salida del terminal:

Salida de terminal números primos

Es importante revisar el código y la salida, porque no sería la primera vez que por un punto o una coma se nos va al garete el algoritmo. A mi se me colaron un 5, un 9, un 15 y un 25 en un archivo con números primos hasta el 1000000, ¡y tuve que comprobar que el resto estaba bien rehaciendo el programa!

Si tienes alguna idea, sugerencia, ocurrencia, o simplemente quieres preguntar algo, comenta, mándame un mail o contacta conmigo por redes sociales, y nos vemos en el próximo post.