Análisis de diferentes métodos para encontrar números primos en Python

Si participa en la programación competitiva, es posible que esté familiarizado con el hecho de que las preguntas relacionadas con los números primos son una de las opciones del planteador de problemas. Aquí, discutiremos cómo optimizar su función que verifica el número primo en el conjunto de rangos dado, y también calculará los tiempos para ejecutarlos.

Por definición, un número primo es un número entero positivo que solo es divisible por sí mismo y por 1. Por ejemplo: 2,3,5,7. Pero si un número se puede descomponer en números más pequeños, se llama número compuesto. Por ejemplo: 4=2*2, 6=2*3

Y el entero 1 no es un número primo ni un número compuesto. Verificar que un número es primo es fácil, pero verificar de manera eficiente requiere un poco de esfuerzo.

Método 1:

 
Vayamos ahora con la primera función para verificar si un número, digamos n, es primo o no. En este método, probaremos todos los divisores de 2 a n-1. Saltaremos 1 y n. Si n es divisible por cualquiera de los divisores, la función devolverá False, de lo contrario True. 
Los siguientes son los pasos utilizados en este método: 

1. Si el entero es menor que igual a 1, devuelve False.
2. Si el número dado es divisible por cualquiera de los números del 2 al n, la función devolverá False
3. De lo contrario, devolverá True

# Python Program to find prime numbers in a range
import time
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Producción: 

Total prime numbers in range: 9592
Time required: 60.702312707901

En el código anterior, verificamos todos los números del 1 al 100000, ya sea que esos números sean primos o no. Tiene un gran tiempo de ejecución como se muestra. Tarda alrededor de 1 minuto en ejecutarse. Este es un enfoque simple pero lleva mucho tiempo ejecutarlo. Por lo tanto, no se prefiere en la programación competitiva.

Método 2:

 
En este método, usamos un truco simple al reducir la cantidad de divisores que buscamos. Hemos encontrado que hay una línea fina que actúa como un espejo que muestra la factorización por debajo de la línea y la factorización por encima de la línea en orden inverso. La línea que divide los factores en dos mitades es la línea de la raíz cuadrada del número. Si el número es un cuadrado perfecto, podemos desplazar la línea en 1 y si podemos obtener el valor entero de la línea que divide. 

36=1*36          
  =2*18
  =3*12
  =4*9
------------
  =6*6
------------
  =9*4
  =12*3
  =18*2
  =36*1

En esta función, calculamos un número entero, digamos max_div, que es la raíz cuadrada del número y obtenemos su valor mínimo usando la biblioteca matemática de Python. En el último ejemplo, iteramos de 2 a n-1. Pero en esto, reducimos los divisores a la mitad como se muestra. Debe importar el módulo de matemáticas para obtener la función Floor y sqrt. 
Los siguientes son los pasos utilizados en este método: 

1. Si el entero es menor que igual a 1, devuelve False.
2. Ahora, reducimos los números que deben verificarse a la raíz cuadrada del número dado.
3. Si el número dado es divisible por cualquiera de los números desde 2 hasta la raíz cuadrada del número, la función devolverá False
4. De lo contrario, devolverá True

# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
    if n <= 1:
        return False
 
    max_div = math.floor(math.sqrt(n))
    for i in range(2, 1 + max_div):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Producción:  

Total prime numbers in range: 9592
Time required: 0.4116342067718506

En el código anterior, verificamos todos los números del 1 al 100000, ya sea que esos números sean primos o no. Toma comparativamente menos tiempo que el método anterior. Este es un enfoque un poco complicado, pero hace una gran diferencia en el tiempo de ejecución del código. Por lo tanto, es más preferido en la programación competitiva. 
 

Método 3:

 
Ahora, optimizaremos nuestro código al siguiente nivel, lo que lleva menos tiempo que el método anterior. Es posible que haya notado que en el último ejemplo, iteramos a través de cada número par hasta el límite, lo cual fue un desperdicio. Lo que hay que notar es que todos los números pares, excepto dos, no pueden ser números primos. En este método, descartamos todos los números pares para optimizar nuestro código y verificaremos solo los divisores impares. 
Los siguientes son los pasos utilizados en este método: 

1. Si el entero es menor que igual a 1, devuelve False.
2. Si el número es igual a 2, devolverá True.
3. Si el número es mayor que 2 y divisible por 2, devolverá Falso.
4. Ahora, hemos comprobado todos los números pares. Ahora, busca los números impares.
5. Si el número dado es divisible por cualquiera de los números desde 3 hasta la raíz cuadrada del número saltándose todos los números pares, la función devolverá False
6. De lo contrario, devolverá True

# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n > 2 and n % 2 == 0:
        return False
 
    max_div = math.floor(math.sqrt(n))
    for i in range(3, 1 + max_div, 2):
        if n % i == 0:
            return False
    return True
 
# Driver function
t0 = time.time()
c = 0 #for counting
 
for n in range(1,100000):
    x = is_prime(n)
    c += x
print("Total prime numbers in range :", c)
 
t1 = time.time()
print("Time required :", t1 - t0)

Producción:  

Total prime numbers in range: 9592
Time required: 0.23305177688598633

En el código anterior, verificamos todos los números del 1 al 100000, ya sea que esos números sean primos o no. Toma comparativamente menos tiempo que todos los métodos anteriores para ejecutar el programa. Es la forma más eficiente y rápida de verificar el número primo. Por lo tanto, es el más preferido en la programación competitiva. La próxima vez que intente cualquier pregunta en la programación competitiva, use este método para obtener mejores resultados.
 

Método de tamiz: 

Este método imprime todos los primos menores o iguales a un número dado, n. Por ejemplo, si n es 10, la salida debería ser «2, 3, 5, 7». Si n es 20, la salida debe ser «2, 3, 5, 7, 11, 13, 17, 19». 
Este método se considera el método más eficiente para generar todos los números primos menores que el número dado, n. Se considera como el método más rápido de todos para generar una lista de números primos. Este método no es adecuado para verificar un número en particular. Este método es el preferido para generar la lista de todos los números primos.

# Python Program to find prime numbers in a range
import time
def SieveOfEratosthenes(n):
      
    # Create a boolean array "prime[0..n]" and
    # initialize all entries it as true. A value
    # in prime[i] will finally be false if i is
    # Not a prime, else true.
    prime = [True for i in range(n+1)]
     
    p = 2
    while(p * p <= n):
          
        # If prime[p] is not changed, then it is
       # a prime
        if (prime[p] == True):
              
            # Update all multiples of p
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    c = 0
 
    # Print all prime numbers
    for p in range(2, n):
        if prime[p]:
            c += 1
    return c
 
# Driver function
t0 = time.time()
c = SieveOfEratosthenes(100000)
print("Total prime numbers in range:", c)
 
t1 = time.time()
print("Time required:", t1 - t0)

Producción: 

Total prime numbers in range: 9592
Time required: 0.0312497615814209

Nota: el tiempo requerido para todos los procedimientos puede variar según el compilador, pero el orden de tiempo requerido por los diferentes métodos seguirá siendo el mismo.

Referencia : 

\https://www.geeksforgeeks.org/sieve-of-eratosthenes/ 
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
Este artículo es una contribución de Rishabh Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.