Verificación de números primos en Python

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

Realizar la verificación de un número primo es uno de los problemas clásicos que se suelen analizar cuando se inicia en la programación iterativa. Es típico que se desarrollen algoritmos para la validación de números primos en esta fase. En este artículo, analizamos al detalle y paso a paso, algoritmos para determinar números primos en Python presentando 6 alternativas de solución a través de diversas versiones usando estructuras algorítmicas iterativas. Si deseas conocer con más detalle la definición de número primo usada en este problema, haz click en el siguiente enlace.

Parte de esta análisis se encuentra sintetizado en el vídeo «Verificación de Números Primos en Python» en nuestro canal de YouTube. Te invitamos a que lo visites.

A continuación presentamos 6 alternativas de solución que nos permitirá entender cómo se verifica un número es primo en Python. Se analizará cada alternativa con sumo detalle desde el punto de vista del pensamiento computacional. Las versiones que se analizarán son las siguientes:

  • Versión contando divisores.
  • Versión contando divisores optimizando el rango de iteración.
  • Versión buscando divisores.
  • Versión buscando divisores optimizando el rango de iteración con la mitad.
  • Versión buscando divisores optimizando el rango de iteración con la raíz cuadrada.
  • Versión usando el Teorema de Wilson.

Resolución del problema: versión contando divisores

La primera alternativa de solución que analizaremos será por conteo de divisores. El algoritmo que usaremos en este caso se divide en dos partes. En la primera parte contaremos la cantidad de divisores que posee el número. En la segunda parte verificaremos si la cantidad de divisores contados corresponde con la que debería tener un número primo. Sabemos que un número primo solo puede tener dos divisores.

Analizaremos esta alternativa de solución detallando las siguientes secciones:

  • Lectura del dato de entrada.
  • Validación del dato de entrada.
  • Control de flujo de la iteración.
  • Inicialización del acumulador de divisores.
  • Acumulación de divisores.
  • Determinación si el número es primo.

Lectura de datos

La lectura en este problema es bastante simple pues solamente existe un dato de entrada, el número para el cual deseamos verificar si es primo o compuesto. Para la lectura de datos en Python usaremos la función \texttt{input}. Usaremos la variable \texttt{n} para leer el número que vamos a verificar. La variable \texttt{n} la necesitamos como valor entero. Por este motivo, usamos la función \texttt{int} para transformar la cadena de caracteres que se lee, en un valor entero. 

n=int(input("Ingrese un número natural (>0): ")) 

Validación de datos de entrada

Procedemos ahora a hacer la validación del dato de entrada. Como en el enunciado se indica que \texttt{n} es un número natural, debemos verificar que él mismo sea mayor que cero. 

Haremos que nuestro algoritmo tome una decisión. Si el número leído es menor o igual a 0, deberemos emitir un mensaje informativo al usuario. La instrucción que permite que un algoritmo tome decisiones sobre qué flujo ejecutar es la estructura algorítmica selectiva. Usaremos una selectiva doble pues tenemos dos posibles caminos a seguir: o emitimos un mensaje de error o realizamos las operaciones de verificación. La condición a usar será \texttt{n<=0}.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else: 

Control de flujo de la iteración

Como ya se ha comentado previamente, el problema de determinar números primos, se puede dividir en dos partes o dos sub problemas. La primera parte corresponde con contar cuántos divisores posee un número. La segunda parte corresponde con verificar si la cantidad de divisores que hemos contado es exactamente dos.

Comenzaremos con la primera parte, ¿cómo contamos los divisores de un número? Pues probando todos los números en el rango [1..n], verificando si el resto de la división entera entre \texttt{n} y el número en cuestión es igual a cero. Si el resto es cero, el número será divisor de \texttt{n}. Pero, ¿por qué ese rango? Pues por que si n tiene divisores, estos se encontrarán en dicho rango de valores. Matemáticamente es imposible que n tenga divisores fuera de dicho rango.

Como se debe recorrer el rango [1..n] y hacer siempre la misma verificación (si es divisor o no) una y otra vez. Se debe utilizar una estructura iterativa. Procederemos en esta sección a realizar el control de flujo de dicha iteración. Usaremos para ello un ciclo iterativo con entrada controlada y configuraremos el control por variable siguiendo los siguientes pasos:

  1. Inicializamos la variable de control. En este caso hemos definido la variable de control \texttt{i} y la hemos inicializado con el valor de \texttt{1}. La inicializamos con este valor por las condiciones del problema. Esto pues, vamos a contar los divisores que tiene el número \texttt{n} en el rango [1..n]
  2. Controlamos el flujo usando la variable de control. Como tenemos que visitar los \texttt{n} números  en el rango [1..n], la variable de control \texttt{i} debe actualizarse con  \texttt{n} valores, desde \texttt{1}, su valor inicial, hasta \texttt{n}, su valor final. Por lo tanto la condición de repetición es \texttt{i<=n}. Mientras esto sea verdad, se seguirá repitiendo y se podrá hacer la verificación.
  3. Actualizamos el valor de la variable de control. Debemos cambiar la variable de control para que el ciclo iterativo no se haga infinito. Debemos garantizar que en algún momento en el tiempo, la condición se evalúe como falsa. Por lo tanto debemos incrementar \texttt{i} para que llegue a ser mayor que \texttt{n} y el ciclo termine. Por condiciones del problema, se incrementará en 1 a la variable de control. Para el caso del incremento, se ha usado el operador de asignación \texttt{+=}. \texttt{i+=1} equivale a la instrucción \texttt{i=i+1}.
n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    i = 1
    while (i <= n):
        
        i+=1 

Inicialización del acumulador de divisores

Una vez gestionado el control de flujo, procederemos a acumular los divisores del número. Para esto usaremos la variable \texttt{cant\_divisores} y la inicializamos con el valor de \texttt{0}. Inicializamos la variable con este valor pues como vamos a contar, se requiere como valor inicial el elemento neutro para la suma.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    cant_divisores = 0
    i = 1
    while (i <= n):
        
        i+=1 

Acumulación de divisores

Procederemos ahora a contar los divisores. ¿Cómo sabemos si estamos frente a un divisor? Bueno, para que un número sea divisor de otro, no debe existir resto cuando se divida entre él. En Python existe el operador \texttt{\%} que retorna el resto o módulo de la división entera entre dos números. En particular, la expresión \texttt{n\ \%\ i} retorna el resto de la división entera de \texttt{n} entre \texttt{i}. Si el resto es \texttt{0} quiere decir que hemos encontrado un divisor y podremos afirmar que \texttt{i} es divisor de \texttt{n}.

¿Cómo hacemos la acumulación? Cuando se encuentre un divisor, el algoritmo tomará una decisión, incrementar en uno la variable \texttt{cant\_divisores}. Y, ¿si no encuentra el divisor? Pues, no hace nada. No nos interesa controlar cuando no se encuentre un divisor. Por este motivo usamos una selectiva simple para hacer la acumulación.

¿Dónde colocamos la acumulación? Como es una acción repetitiva, debemos colocarla dentro de la iteración. Inicialmente \texttt{i} vale \texttt{1}, por lo que si \texttt{n\ \%\ 1} retorna \texttt{0}, diremos que \texttt{1} es divisor de \texttt{n}. Luego,  \texttt{i} vale \texttt{2}, por lo que si \texttt{n\ \%\ 2} retorna \texttt{0}, diremos que \texttt{2} es divisor de \texttt{n}.  Cuando \texttt{i} vale \texttt{3}, si \texttt{n\ \%\ 3} retorna \texttt{0}, diremos que \texttt{3} es divisor de \texttt{n}. Y esto lo hacemos mientras \texttt{i<=n}. Cada vez que identificamos un divisor, incrementamos \texttt{cant\_divisores} en \texttt{1}.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    cant_divisores = 0
    i = 1
    while (i <= n):
        if n % i == 0:
            cant_divisores+=1
        i+=1 

Determinación si el número es primo

Procederemos ahora a determinar si el número es primo. Como comentamos anteriormente, este paso corresponde con la segunda parte del problema y lo realizaremos cuando terminemos de contar los divisores del número en cuestión. Esto es importante notar pues, este paso debe ir después de terminar la iteración. No puede ir dentro del ciclo iterativo pues dentro del ciclo estamos recién contando los divisores.

Dicho esto, para determinar si un número es primo, basta verificar la condición \texttt{cant\_divisores==2}. Como nos han solicitado emitir un mensaje cuando el número es primo y otro cuando no lo sea, usaremos para este fin, una selectiva doble.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    cant_divisores = 0
    i = 1
    while (i <= n):
        if n % i == 0:
            cant_divisores+=1
        i+=1
    if cant_divisores==2:
        print("El número es primo")
    else:
        print("El número no es primo") 

Resolución del problema: versión contando divisores optimizando el rango de iteración

Realizaremos ahora una variación a la alternativa de solución con la intención de optimizar el rango de la iteración. Cambiaremos básicamente tres cosas. Primero, la inicialización de la variable de control, luego, cambiamos la condición de la iteración y  finalmente, afinamos la condición para verificar si un número es primo o compuesto.

Empecemos con la modificación del control de flujo. Analicemos una situación matemática que es trivial y que ayudará a que mejoremos un poco nuestro algoritmo. Independiente de si el número \texttt{n} es primo o no, siempre será divisible por 1 y por si mismo. Entonces, ¿para qué los contamos?¿por qué no los dejamos de contar?, Pues eso es efectivamente lo que vamos a hacer, en lugar de recorrer el rango [1..n], recorreremos el rango [2..n-1]. Pero, ¿cómo sabremos si el número es primo? Pues muy fácil, en dicho rango no debe existir ningún divisor. Por lo que la condición para determinar si el número es primo ahora cambia a \texttt{cant\_divisores=0}. Con esta versión del algoritmo nos ahorramos un par de iteraciones. 

Ahora, recordemos que el número 1 no es primo. Si analizamos el algoritmo con los cambios propuestos, veremos que cuando se analice el número 1, la cantidad de divisores de este será de 0 por lo que debemos incluir la condición \texttt{n>1} al momento de determinar si el número es primo o no.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    cant_divisores = 0
    i = 2
    while (i < n):
        if n % i == 0:
            cant_divisores+=1
        i+=1
    if cant_divisores==0 and n>1:
        print("El número es primo")
    else:
        print("El número no es primo") 

Resolución del problema: versión buscando divisores

La siguiente alternativa de solución que analizaremos será por búsqueda de divisores. El algoritmo que usaremos en este caso se divide también en dos partes. En la primera parte buscamos si existen divisores diferentes de 1 y del mismo número. En la segunda parte verificamos si el número es primo: si no se han encontrado divisores adicionales, el número será primo, en caso contrario será un número compuesto.

Analizaremos esta alternativa de solución detallando las siguientes secciones:

  • Inicialización de la bandera o flag.
  • Búsqueda de divisores.
  • Determinación si el número es primo.

Inicialización de la bandera

Recordemos el objetivo del problema, nos indican que determinemos si el número es primo o no. No nos están pidiendo que retornemos los divisores ni que los contemos, por lo que basta que encontremos un divisor en el rango [2..n-1] para que podamos afirmar que el número no es primo. Entonces si encontramos uno, podemos parar de iterar. Ya no tiene sentido continuar la iteración y gastar tiempo de CPU en cálculos que no van a modificar en nada la respuesta final. Da igual si encontramos 1, 2, 3 o x divisores.

Para esto usaremos una bandera o flag. Hemos nombrado la bandera con el identificador \texttt{encontro\_divisores}. Hemos inicializado esta bandera con el valor de \texttt{False}. Esto significa que no hemos encontrado ningún divisor en el rango. Apenas encuentre uno, levantamos la bandera, es decir, asignaremos el valor de \texttt{True} a dicha variable.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    encontro_divisores = False 

Búsqueda de divisores

Pero, ¿cómo se usa la bandera en el control de flujo? La usaremos para detener el ciclo iterativo en caso se haya encontrado un divisor. Si encuentra uno, se deja de buscar. Como puede notar la condición ahora es \texttt{i<n\ and\ not\ encontro\_divisores}. Es decir que realizaremos la iteración mientras no se encuentren divisores. Si encuentro un divisor, no importa que \texttt{i<n}, no tiene sentido continuar iterando pues pase lo que pase, ya sabemos que el número no es primo.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    encontro_divisores = False    
    i = 2
    while (i < n and not encontro_divisores):
        if n % i == 0:
            encontro_divisores = True
        i+=1 

Determinación si el número es primo

Para determinar si un número es primo, basta verificar que no se hayan encontrado divisores adicionales a si mismo y la unidad. Esto significa que la variable \texttt{encontro\_divisores} debe contener el valor de \texttt{False}. Hay que recordar nuevamente que el número 1 no es un número primo por lo que debe incluirse esto en la condición de la selectiva.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    encontro_divisores = False    
    i = 2
    while (i < n and not encontro_divisores):
        if n % i == 0:
            encontro_divisores = True
        i+=1
    if not encontro_divisores and n>1:
        print("El número es primo")
    else:
        print("El número no es primo") 

Resolución del problema: versión buscando divisores optimizando el rango de iteración con la mitad

Veamos ahora otra optimización del algoritmo. Tiene que ver con las matemáticas también. Si un número n posee un divisor, este se encontrará en el rango [1..\frac{n}{2}]. No existe ningún divisor de n que sea mayor a \frac{n}{2}. Podemos usar este conocimiento matemático para optimizar el algoritmo y reducir así la cantidad de iteraciones.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    encontro_divisores = False    
    i = 2
    while (i <= n//2 and not encontro_divisores):
        if n % i == 0:
            encontro_divisores = True
        i+=1
    if not encontro_divisores and n>1:
        print("El número es primo")
    else:
        print("El número no es primo") 

Resolución del problema: versión buscando divisores optimizando el rango de iteración con la raíz cuadrada

Veamos ahora la última versión. Tiene que ver con matemáticas de nuevo, pero en este caso no es tan trivial como el anterior. Para determinar si un número es primo o no, basta con verificar si el número no es divisible por otros primos en el rango [2..\sqrt{n}]. Usaremos este conocimiento para optimizar aún más el algoritmo. Recuerde que la función \texttt{sqrt} permite obtener la raíz cuadrada del valor pasado como parámetro. 

import math

n=int(input("Ingrese un número natural (>0): "))

if n <= 0:
    print("El número debe ser mayor que cero")
else:
    encontro_divisores = False    
    i = 2
    while (i <= math.sqrt(n) and not encontro_divisores):
        if n % i == 0:
            encontro_divisores = True
        i+=1
    if not encontro_divisores and n>1:
        print("El número es primo")
    else:
        print("El número no es primo") 

Resolución del problema: versión usando el Teorema de Wilson

La última versión que veremos es la implementación del Teorema de Wilson. Este teorema indica que un número n es primo si (n-1)!+1 es divisible entre n. La solución de este teorema no es complicada de realizar. Usamos una productoria para acumular el factorial en un ciclo iterativo y al final se utiliza una selectiva doble para realizar la verificación usando la fórmula antes mencionada.

Pero, como casi siempre en la programación, lo fácil sale caro. Los factoriales suelen se números muy grandes por que lo que si queremos implementar esta solución en Python, solo podremos comprobar los 20 primeros números.

n=int(input("Ingrese un número natural (>0): "))

if n <= 0 or n>20:
    print("El número debe estar entre [1..20]")
else:
    factorial = 1
    i = 2
    while (i < n):
        factorial *= i;
        i+=1
    if (factorial + 1) % n == 0 and n > 1:
        print("El número es primo")
    else:
        print("El número no es primo") 

Conclusión

Hemos presentado en este artículo, 5 propuestas de solución para la verificación de un número primo. Se ha utilizado para el control de flujo la estructura iterativa y realizándose el control mediante un ciclo con entrada controlada. Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema en PSeInt y otros lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si te interesa profundizar más en el desarrollo en Python, los dos mejores libros que se han escrito son Learning Python de Mark Lutz y Python Crash Course de Eric Matthes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *