Puede descargar el archivo:
primos.py
Veamos diferentes métodos para calcular números primos en Python.
Método 1
Creamos dos funciones, la primera detecta si un número es primo o no, y la segunda crea un listado de números primos hasta 100.
#Función que detecta si un número es primo
import math
def esPrimo(num):
for i in range(3,int(math.sqrt(num))+1,2):
if num%i==0:
return False
return True
def listaPrimos(limite):
print(2)
for j in range(3,limite+1,2):
if esPrimo(j):
print(j)
listaPrimos(100)
La expresión
if num%i==0 también se puede sustituir por la expresión
if num/i%1==0 que hace el mismo trabajo.
Para optimizar el algoritmo los bucles únicamente trabajan con los impares, ya que salvo el 2, todos los demás primos son impares.
Otra forma de optimizar el algoritmo consiste en hacer que el bucle interior que detecta si un número es primo calcule el resto de dividir ese número entre todos los anteriores pares únicamente hasta la raíz cuadrada de ese mismo número. Esto es así ya que si llegamos dividiendo hasta la raíz cuadrada de ese número y no hemos encontrado ninguna división exacta, superada la raíz cuadrada ya es imposible que encontremos esa división exacta.
Método 2
Crear una lista de números primos y añadir el siguiente con
append.
import math
lista=[2,]
for i in range(3,100, 2):
soy=True #inicialmente suponemos que el número es primo
for j in range(3,int(math.sqrt(i))+1,2):
if i%j==0:
soy=False
if soy:lista.append(i)
print(lista)
Método 3
Este método es muy similar al anterior pero más corto ya que nos ahorramos crear la variable booleana
soy, y trabajar al final con ella en un
if. Lo que hacemos en este caso es usar solo el primer if con un
break y luego un
else con una indentación sorprendente.
lista=[2,]
for i in range(3,100,2):
for j in range(3,int(i**.5)+1,2):
if i%j==0:
break
else: # else del for
lista.append(i)
print(list(lista))
Método 4
Este método es similar al anterior pero no usa una lista, simplemente imprime los resultados separados por coma.
print(2, end = ',')
for i in range(3,150,2):
for j in range(3,int(i**.5)+1,2):
if i%j==0: break
else: print(i, end = ',')
Método 5
Usando un generador con
yield.
#Método 4
from math import sqrt
def esPrimo(n):
for i in range(3,int(sqrt(n))+1,2):
if n%i==0:
return False
return True
def generaPrimos(n):
for i in filter(esPrimo, range(3,n+1,2)):
yield i
print(2)
for i in generaPrimos(100):
print(i)
Podemos sustituir la expresión
if n%i==0: por esta otra
if not(n%i):. El motivo de que podamos hacer esta sustitución y todo continúe funcionando bien es que si una expresión es cero se interpreta como False y si es uno (u otro número) se interpreta como True.
Se utiliza la expresión
filter.
Método 6
Con dos funciones, la primera detecta si un número es primo o no, la segunda va preguntando por los primos en un cierto rango y si resultan ser primos los anota en una lista. Finalmente se imprime la lista.
def isPrime(n):
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return False
return True
def primeList(n):
primes = [2,]
for i in range(3,n,2):
if isPrime(i):
primes.append(i)
return primes
print(primeList(100))
