En busca de los números primos

En esta actividad crearemos un script en Python para implementar la criba de Eratóstenes para números de 1 a n. Podríamos aplicar la criba mediante criterios de divisibilidad para los números desde 2 hasta j, con j entre 1 y n. 

Para el caso anterior el código sería bastante lento, por ello aplicaremos la división solo para valores desde 2 hasta √j (redondeando al próximo entero), de esta forma reducimos bastante el número de iteraciones. En Wikipedia podemos encontrar un pseudocódigo bastante entendible:

Entrada: Un número natural n

Salida: El conjunto de números primos menores o iguales que n

1 Escribir los números entre 2 y n

2 Para cada i desde 2 hasta la parte entera de raíz de n hacemos lo siguiente

  > Si i no ha sido marcado entonces:

  > Para j desde i hasta n/i marcamos i*j

3 El resultado son los números sin marcar.

Esta idea puede ser implementada en Python como la siguiente función

def criba_eratostenes(n):

    #Inicializamos una lista de booleanos para marcar los números

    primos = [True] * (n + 1) #Esta acción genera una lista [] con n veces True

    primos[0] = primos[1] = False #0 y 1 no son primos

    #Iteramos desde 2 hasta la raíz cuadrada de n

    for i in range(2, int(n**0.5) + 1):

        if primos[i]:  #Si i no está marcado

            #Marcamos todos los múltiplos de i como no primos

            for j in range(i * i, n + 1, i):

                primos[j] = False

    #Retornamos los números que no han sido marcados

    return [i for i in range(n + 1) if primos[i]]

Probemos el código

n = 17

resultado = criba_eratostenes(n)

print(f"Los números primos menores o iguales a {n} son: {resultado}")

La salida por pantalla es Los números primos menores o iguales a 17 son: [2, 3, 5, 7, 11, 13, 17].

Podemos modificar un poco el código anterior para crear una función a la que le demos un número y nos diga si es no primo (¿serías capaz?), dejo mi solución a continuación (te dejo como ejercicio comentar adecuadamente el código ;))

def es_primo(n):

    for i in range(2, int(n**0.5) + 1):

        if n % i != 0:

            pass

        else:

          return print(f"El número {n} no es primo")

    return print(f"El número {n} es primo")

Por ejemplo, para n = 1237 la respuesta es El número 1237 es primo. 

• ¿Serías capaz de comprobar si 27343 es primo?

• Modifica el código de la criba para que podamos encontrar números primos entre dos números naturales dados. Es decir, crea una función a la que le demos un número n y otro m y la respuesta sean los números primos entre n y m.

• Crea un código al que le demos una lista de números y nos indique cuáles de ellos son o no primos. Además, haz que podamos elegir si queremos o no que nos devuelva una sublista con los números primos de la lista inicial y otra con los que no lo son.

• Crea un código para factorizar números.

Nota: si necesitas ayuda puedes apoyarte en la IA para entender el código o para pedir alternativas, pero siempre es bueno saber qué hace nuestro código. El código de la Criba podría ser mejorado si para un valor i marcamos en la lista los múltiplos de i, de esta forma estaremos quitando (siempre que se pueda) más de un valor de la lista de posibilidades.

Existen otras alternativas, en Wikipedia podemos leer lo siguiente sobre el método AKS

AKS is the first primality-proving algorithm to be simultaneously general, polynomial-time, deterministic, and unconditionally correct. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four. 

Dejo a continuación un enlace de GitHub donde implementan este método: GitHub - benschlueter/AKS_PrimeTest: AKS Prime Test Python.