Números primos en Python

Esta entrada del blog pertenece a una serie:

• Números primos en Python
• Factorización en Python
• Máximo común divisor (MCD) en Python
• Mínimo común múltiplo (mcm) en Python

Calculemos números primos en Python por varios métodos.

Código en repl.it

Método 1

Dado un número queremos una función que nos diga si es primo retornando True o no es primo retornando False.

#!/bin/python3  
# Detectar si un número es primo o no. Función que dice si un número es primo  
from math import sqrt  
def sera_primo(n): # n es un número mayor que 2   
 primo=True #inicialmente un número es primo hasta que no se demuestre lo contrario   
 for j in range(3,int(sqrt(n)+1),2): #probamos loa imparea hasta llegar a la raiz de n  
  if (n%j==0): #si el módulo es cero se debe a que es divisible y por tanto no es primo   
   primo=False  
   break  
 return primo  
x=199  
print('¿{} es primo? → {}'.format(x,sera_primo(x)))  

Método 2

Vamos a listar todos los primos entre 2 y n.

#!/bin/python3  
# Cálculo de los números primos desde 2 hasta uno dado  
from math import sqrt  
def primos_hasta(n):  
 lista_primos=[2] # el 2 es primo y todos los demás pares no lo son   
 for i in range(3,n+1,2): #tratamos solo los impares  
  primo=True #inicialmente un número es primo hasta que no se demuestre lo contrario   
  for j in range(3,int(sqrt(i)+1),2): #probamos hasta llegar a la raiz cuadrada de i  
   if (i%j==0): #si el módulo es cero se debe a que es divisible y por tanto no es primo   
    primo=False    
    break  
  if primo:  
   lista_primos.append(i)  
 return lista_primos  
print(primos_hasta(1000))  

Método 3

Utilizaremos el algoritmo de la criba de Eratóstenes para obtener todos los primos desde 2 hasta n.

#!/bin/python3  
# Criba de Eratóstenes  https://es.wikipedia.org/wiki/Criba_de_Eratóstenes  
def primos_hasta(n):  
 lista=[*range(2,n+1)] #el operador * desempaqueta el rango  
 i=0 #index de la lista. Es un contador  
 while i< len(lista):  
  j=i+1 #segundo contador  
  while j<len(lista):  
   if lista[j]%lista[i]==0:  
    lista.remove(lista[j])  
   j+=1  
  i+=1     
 return lista  
print(primos_hasta(1000))  

Método 4

Otra forma de obtener la lista de los números primos utilizando la criba de Eratóstenes.

#!/bin/python3  
# otro método para la Criba de Eratóstenes  
# https://es.wikipedia.org/wiki/Criba_de_Eratóstenes  
def primos_hasta(n):  
 lista=[None]*n  
 for i in range(2,n):  
  if i not in lista and lista[i]!=0:  
   lista[i]=i  
   for j in range(i*i,n,i):  
    lista[j]=0  
 primos=[x for x in lista if x!=0]  
 return primos[2:]  
print(primos_hasta(100))  

Método 5

En este caso eliminamos los múltiplos con remove.

def primos_hasta(n):  
 lista=[i for i in range(2,n+1)]  
 for i, k in enumerate(lista):  
  if i<=int(n**.5):  
   for j in lista[i+1:]:  
    if j % k == 0:  
     lista.remove(j)  
 return lista  
print(primos_hasta(200))  

Método 6

Creamos una lista con los números primos en una sola línea de código, con list comprehension.

print([x for x in range(2, 101) if all(x%y for y in range(2, min(x, 11)))])