Generación de números primos en Python

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))