Escriba un programa para generar una lista de todos los números primos menores que 20.
Antes de comenzar, es importante tener en cuenta lo que es un número primo.
- Un número primo tiene que ser un entero positivo
- Divisible por exactamente 2 enteros (1 y sí mismo)
- 1 no es un número primo
Si bien hay muchas formas diferentes de resolver este problema, aquí hay algunos enfoques diferentes.
Enfoque 1: para bucles
# Inicializar una lista
primos = []
para possiblePrime en rango (2, 21):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, posiblePrime):
si es posiblePrime% num == 0:
isPrime = Falso
si isPrime:
primes.append (possiblePrime)
Si observa el ciclo for interno incluido en el rectángulo rojo a continuación, observe que tan pronto isPrime sea ??False, es ineficiente seguir iterando. Sería más eficiente salir del circuito.
Enfoque 2: para bucles con ruptura
El Método 2 es más eficiente que el Método 1 porque, tan pronto como encuentre que un número dado no es un número primo, puede salir del ciclo utilizando el break .
# Inicializar una lista
primos = []
para possiblePrime en rango (2, 21):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, posiblePrime):
si es posiblePrime% num == 0:
isPrime = Falso
descanso
si isPrime:
primes.append (possiblePrime)
El enfoque 2 es mucho más eficiente que el enfoque 1. Por ejemplo, si observa el caso cuando es possiblePrime = 15 , observe que hay mucha menos iteración en el enfoque 2.
Método 3: para bucle, ruptura y raíz cuadrada
El enfoque 2 se benefició de no hacer iteraciones innecesarias en el ciclo for interno. El enfoque 3 es similar, excepto la función de rango interno. Observe que la función de rango interno ahora es el range(2, int(possiblePrime ** 0.5) + 1) .
# Inicializar una lista
primos = []
para possiblePrime en rango (2, 21):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, int (posiblePrime ** 0.5) + 1):
si es posiblePrime% num == 0:
isPrime = Falso
descanso
si isPrime:
primes.append (possiblePrime)
Para explicar por qué funciona este enfoque, es importante tener en cuenta algunas cosas. Un número compuesto es un número positivo mayor que 1 que no es primo (que tiene factores distintos de 1 y sí mismo). Cada número compuesto tiene un factor menor o igual que su raíz cuadrada (prueba aquí ). Por ejemplo, en la imagen de los factores de 15 a continuación, observe que los factores en rojo son solo los reveses de los factores verdes. En otras palabras, por la propiedad conmutativa de la multiplicación 3 x 5 = 5 x 3. Solo necesita incluir los pares verdes para asegurarse de tener todos los factores.
Factores de 15
Comparación del tiempo de diferentes enfoques
Ciertos métodos para generar números primos son más eficientes. Para mostrar esto, estudiemos el tiempo de diferencia de rendimiento entre los enfoques que generan números primos hasta un número dado.
Enfoque 1: para bucles
def approach1 (givenNumber):
# Inicializar una lista
primos = []
para possiblePrime en rango (2, givenNumber + 1):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, posiblePrime):
si es posiblePrime% num == 0:
isPrime = Falso
si isPrime:
primes.append (possiblePrime)
retorno (primos)
Enfoque 2: para bucles con ruptura
def approach2 (givenNumber):
# Inicializar una lista
primos = []
para possiblePrime en rango (2, givenNumber + 1):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, posiblePrime):
si es posiblePrime% num == 0:
isPrime = Falso
descanso
si isPrime:
primes.append (possiblePrime)
retorno (primos)
Método 3: para bucle, ruptura y raíz cuadrada
def approach3 (givenNumber):
# Inicializar una lista
primos = []
para possiblePrime en rango (2, givenNumber + 1):
# Asume que el número es primo hasta que se muestra que no.
isPrime = True
para num en rango (2, int (posiblePrime ** 0.5) + 1):
si es posiblePrime% num == 0:
isPrime = Falso
descanso
si isPrime:
primes.append (possiblePrime)
retorno (primos)
La diferencia de rendimiento se puede medir usando el la timeit biblioteca que le permite el tiempo de su código Python. En este caso, estamos midiendo el tiempo que lleva encontrar números primos hasta 500 para cada enfoque. El siguiente código ejecuta el código para cada aproximación 10000 veces y genera el tiempo total que tomó en segundos.
tiempo de importación
# Método 1: tiempo de ejecución
print (timeit.timeit ('approach1 (500)', globals = globals (), number = 10000))
# Método 2: tiempo de ejecución
print (timeit.timeit ('approach2 (500)', globals = globals (), number = 10000))
# Método 3: tiempo de ejecución
print (timeit.timeit ('approach3 (500)', globals = globals (), number = 10000))
Claramente, Approach 3 es el más rápido.
Observaciones finales
Los tres enfoques definitivamente no son las únicas formas de calcular los números primos, pero es de esperar que las diversas formas de identificar los números primos te hayan ayudado. Los números primos son importantes en teoría de números y métodos criptográficos como el algoritmo rsa. Como siempre, el código en la publicación también está disponible en mi github ( código de aproximación , comparación de tiempo ). Si tiene alguna pregunta o comentario sobre el tutorial, no dude en comunicarse en los comentarios a continuación o a través de Twitter .
