Numeros primos en Python

En matemáticas, un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el.​ Por el contrario, los números compuestos son los números naturales que tienen algún divisor natural aparte de sí mismos y del 1, y, por lo tanto, pueden factorizarse.

Wikipedia

A pesar de esa simple definición, definir si un numero es primo, es una de las tareas mas extenuantes e interesantes en la computación, es decir, el proceso es tan simple como dividir cada uno de los números anteriores a nuestro candidato a numero primo. Esto se vuelve difícil cuando nuestro numero tiene varios millones de dígitos.

Aun así, no podemos brincarnos ese algoritmo, pues es la forma mas simple de entender como funciona, así que sin mas:

def es_primo(num):
    if num > 1:
        for i in range(2, num//2):
            if (num % i) == 0:
                return False
        else:
            return True

es_primo(18)
False
es_primo(17)
True

Aquí vemos un concepto curioso, el else luego de un for, que no significa otra cosa mas que ejecuta el siguiente código si y solo si el for termino correctamente.

El código anterior crea un rango del dos hasta la mitad entera del numero a comprobar, para luego comprobar si existe algún residuo de la división entre el numero y cada uno de los elementos de nuestro rango. en caso de que no, sabremos que el numero es primo y nos regresa un True.

Criba de eratostenes

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.

Wikibooks

Tal como lo menciona wikibooks, la criba de eratostenes es un método para obtener un rango de números primos, lo único que tenemos que hacer, una y otra vez, es tomar el primer numero no tachado, y tachar todos sus múltiplos, hasta que completemos la lista, en esta ocasión tomare el mismo código que aparece en el sitio.

def criba_eratostenes(n):
    multiplos = set()
    for i in range(2, n+1):
        if i not in multiplos:
            multiplos.update(range(i*i, n+1, i))
            print(i, end=" ")

criba_eratostenes(10)
2 3 5 7

Como podrás notar, el conjunto en la que se van tachando los elementos es múltiplos, pues verifica que no exista el numero y luego lo imprime. Como dato rápido, un conjunto en python (set) es una lista no ordenada de elementos no repetidos, tienen las mismas reglas que los conjuntos matemáticos. En futuras entradas hablare de ellos.

Usar un generator para producir números primos en Python

Es común que en las entrevistas de python te soliciten el uso de generators, por lo que un ejemplo practico muy bueno es el crear un generator para escupir N números primos, gracias al código que vimos anteriormente lo único que necesitamos hacer es intercambiar nuestro print por un yield.

def generador_primos(n):
    for num in range(2, n + 1):
        if num > 1:
            for i in range(2, num):
                if (num % i) == 0:
                    break
            else:
                yield num

p = generador_primos(10)
print(next(p))
2
print(next(p))
3
print(next(p))
5

La función anterior nos retorna un objeto generator, el cual puede ser iterado en un for, convertirlo en una lista, o incluso obtener el siguiente elemento con el uso de next().

Eso es todo por hoy, si tienes alguna duda puedes dejarla en la caja de comentarios, hasta la próxima!