Validar si un número es primo en Python

  En esta entrada estaré compartiendo como validar si un número es primo o no en Python, primeramente estaré definiendo que es un número primo.

¿Qué es un número primo?

Los números primos son aquellos que solo son divisibles entre ellos mismos y el 1, es decir, que si intentamos dividirlos por cualquier otro número, el resultado no es entero. Dicho de otra forma, si haces la división por cualquier número que no sea 1 o él mismo, se obtiene un resto distinto de cero.

Solución

Luego de ver la definición de un número primo, veremos como programar una función que retorne verdadero si un número es primo o no. Será mostrado de dos formas, con recursividad y con iteración.

Iteración 

Para esta solución haremos una función que recibirá un número y creará una variable llamada contador que inicia en 0. Luego de eso va entrar a un ciclo for que irá de 1 al número + 1, donde aumentará el contador en uno cuando el número sea divisible entre la variable de iteración (recuerde que en Python eso se valida si el residuo da 0, numero%variable==0), cuando termina el ciclo consulta si el contador fue mayor a dos, esto significa que el número tiene dos divisores, el 1 y el mismo, por lo tanto retorna verdadero ya que es primo. De lo contrario, retorna falso, ya que tiene más de dos divisores.

def es_primo(n):
    contador=0
    for i in range(1,n+1):
        if(n%i==0):
            contador+=1
    if(contador==2):
        return True
    else:
        return False

Recursividad

De esta forma cambia un poco e incluso es más eficiente con iteración. Esta solución se compone de dos funciones:

1. es_primo: esta función recibe el número por validar y consulta si es menor a 2, si lo es es por que es 1, 0 o un número negativo, por lo tanto, es falso, o sea no es primo. Si el número es 2 pues retorna verdadero porque es primo. Si es algo diferente a los primeros casos entonces se debe evaluar en la siguiente función, entonces se envía el número por validar y un 2, donde inicia el contador.

2. es_primo_aux: esta función auxiliar recibe el número por validar y una variable divisor, la función inicia consultando si el número de entrada es igual al divisor, si lo es, retorna true ya que cumple la condición para ser primo. Si no cumple esa primera condición verifica si el residuo entre el número y el divisor es igual a 0, si lo es entonces el número no es primo y retorna false. Si no cumple esa condición, vuelve a llamar esta función (es_primo_aux) y le envía de parámetro el número y el divisor +1.

def es_primo(n):
    if(n<2):
        return False
    if(n==2):
        return True
    else:
        return es_primo_aux(n,2)

def es_primo_aux(n,divisor):
    if(n==divisor):
        return True
    else:
        if(n%divisor==0):
            return False
        else:
            return es_primo_aux(n,divisor+1)

Conclusión

Para realizar esta funcionalidad existen varías maneras de realizar y queda a su decisión por cual optar, existen cursos en carreras con programación que piden una solución con recursividad para probar la forma de pensar fuera de la caja de los estudiantes, sin embargo, la mejor forma sería con iteración e incluso se puede hacer aún más óptimo, les dejo eso de tarea, ¿Como hacer la función de iteración compartida más eficiente?