Si te refieres a simplemente optimizar tu algoritmo de división por tentativa hay algunas mejoras importantes que puedes hacer y que son muy simples:
Calcular el resto de la división solo con los impares y el 2. Ten en cuenta que los posibles factores van a ser primos y no hay primos pares por definición(menos el 2).
Tampoco es necesario comprobar desde 2 hasta n
, basta con hacerlo hasta la raiz cuadrada de n
. Esto es así porque de ser un número compuesto siempre hay, al menos, un factor que es menor o igual a la raiz cuadrada. Si encontramos un divisor ya sabemos que es compuesto.
Puedes también usar un generador junto a any
.
Tu función puede quedar:
def es_primo(n):
# Comprobamos si n es 2 (unico primo par)
if n == 2:
return True
# Comprobamos si es menor de 2 o es par
if n < 2 or not n % 2:
return False
# Comprobamos si es divisible entre cualquier entero impar entre 3 y sqrt(n)
return not any(n % i == 0 for i in range(3, int(n**0.5) + 1, 2))
La clave está en range
, el primer parámetro (start) es 3, el segundo (stop) es la raíz cuadrada de n
más 1 y el tercer parámetro (step) es 2. Esto hace que el range
genere una secuencia de número impares que empieza en 3 y va de dos en dos hasta raíz cuadrada de n
. Para n = 70
generaría (3, 5, 7)
.
n**0.5
es equivalente a hacer la raíz cuadrada de n
.
any
retorna retorna True
en el momento que alguna de las condiciones se cumple, en este caso en el momento que algún resto es 0.
Para números grandes va a ser un método lento obviamente. En estos casos hay múltiples test de primalidad que podemos implementar que pueden ser más o menos complejos, eficientes o ser deterministas o probabilisticos (test de Fermat, test de Miller-Rabin, AKS, etc).
Si por casualidad tu finalidad es obtener una lista de número primos desde 2 hasta un número dado, una criba de Eratóstenes es muy fácil de implementar y da buenos resultados siempre que n
no sea exageradamente alto.