Retomando problemas del proyecto Euler, este en principio es bastante fácil.
https://projecteuler.net/problem=37
Es relativamente fácil, por ejemplo, con Python, convertir el número a string, ir quitando caracteres por la derecha y comprobando cada vez si el número que queda es primo. Luego, lo mismo por la izquierda.
Mi primera implementación no tuvo en cuenta que no se considera "truncatable" si terminas con un 1. Lo mismo deberían decirlo en el enunciado, lo mismo es falta de cultura matemática por mi parte.
La función is_truncable, que se muestra a continuación, utiliza una función is_prime para trabajar. Va probando casos para probar que los números que van quedando son primos o no. Si después de analizar por la derecha y la izquierda todos han resultado ser primos, asume que es "truncable".
def is_truncable(number):
str_number = str(number)
# 2, 3, 5, 7 no son truncables
if number < 11:
return False
# si empieza o acaba en 1, no es truncable
elif str_number[0] == '1' or str_number[-1] == '1':
return False
else:
# Por la derecha
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[:-1]
# Por la izquierda
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[1:]
return True
Antes de eso, hemos hecho una pequeña función para generar una lista de números primos:
def next_prime(start):
next = start + 1
while not is_prime(next):
next += 1
return next
Y una función main() que monta todo el proceso:
def main():
truncables = []
next = 10;
# nos piden los 11 primeros truncables
while len(truncables) < 11:
next = next_prime(next, is_prime)
if (is_truncable(next, is_prime)):
truncables.append(next)
print("Truncables:", truncables)
print("Sum. truncables =", sum(truncables))
1ª versión malísima
En la primera implementación de is_prime() que hice, sin ninguna optimización, propia de un estudiante de ESO, simplemente iba dividiendo el número en cuestión por todos los números más pequeños que él mismo, si encontraba algún divisor, entonces no era primo.
def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
number_test = number - 1;
while number_test > 1:
resto = number % number_test
if resto == 0:
return False
number_test -= 1;
return True
Los problemas que plantean en proyecto Euler están muy bien pensados. Usando esta implementación ingenua, al llegar al 10º número truncable de la lista, se quedaba el problema clavado.
4ª versión, usando librerías externas
Nos vamos al extremo contrario, usamos alguna librería existente (que seguramente esté bien optimizada y programada) para saber si un número es primo o no. El módulo sympy define una función isprime().
import sympy
def is_prime(number):
return sympy.isprime(number)
Con esta implementación, el problema se resuelve en un tiempo más que razonable, pero no vale, estamos haciendo trampa.
2ª versión: mejor, pero sigue siendo mala
Esta implementación trata de ser un poco mejor: solo comprueba divisores hasta la mitad del número y hace una comprobación previa para los pares:
def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
for n in range(2, int(number/2)):
if number % n == 0:
return False
return True
Tampoco consigue resolver el problema en un tiempo razonable.
3ª versión: razonablemente buena
La siguente implementación de is_prime(), sin ser un prodigio, ya es bastante más óptima:
- Hace una primera prueba contra los divisores más pequeños que ya sabemos que son primos.
- Si es par, no es primo.
- Para números mayores que 5, solo hace las comprobaciones hasta la raíz cuadrada + 1 del número + 1 en cuestión, y sólo comprueba con divisores impares.
def is_prime(number):
if number <= 3 or number == 5:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
return False;
for n in range(5, int(math.sqrt(number)) + 1, 2):
if number % n == 0:
return False
return True
Con esta implementación un poco mejorada, ya tenemos tiempos de resolución del problema razonables y del mismo orden de magnitud que usando la librería sympy.
Para poder hacer todas las diferentes pruebas, he metido todo el código común en un módulo y desde el script principal, pasamos la función is_prime correspondiente.
# Fichero euler37lib.py
def next_prime(start, is_prime):
next = start + 1
while not is_prime(next):
next += 1
return next
def is_truncable(number, is_prime):
str_number = str(number)
# 2, 3, 5, 7 no son truncables
if number < 11:
return False
# Si empieza o acaba en 1, no es truncable
elif str_number[0] == '1' or str_number[-1] == '1':
return False
else:
# Por la derecha
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[:-1]
# Por la izquierda
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[1:]
return True
def main(is_prime):
truncables = []
next = 10;
# Nos piden los 11 primeros truncables
while len(truncables) < 11:
next = next_prime(next, is_prime)
if (is_truncable(next, is_prime)):
truncables.append(next)
print("Truncables:", truncables)
print("Sum. truncables =", sum(truncables))
Y aquí están las cuatro diferentes implementaciones. Primero, haciendo trampa.
# Fichero 037-sympy.py
import sympy
import euler37lib
def is_prime(number):
return sympy.isprime(number)
if __name__ == '__main__':
euler37lib.main(is_prime)
Refinando un poco el algoritmo:
# Fichero 037-refinado.py
import math
import euler37lib
def is_prime(number):
if number <= 3 or number == 5:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
return False;
for n in range(5, int(math.sqrt(number)) + 1, 2):
if number % n == 0:
return False
return True
if __name__ == '__main__':
euler37lib.main(is_prime)
Implementación ligeramente mejor a la ingenua, pero aún así impracticable:
# Fichero 037-pasable.py
import euler37lib
def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
for n in range(2, int(number/2)):
if number % n == 0:
return False
return True
if __name__ == '__main__':
euler37lib.main(is_prime)
Implementación ingenua:
# Fichero 037-ingenuo.py
import euler37lib
def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
number_test = number - 1;
while number_test > 1:
resto = number % number_test
if resto == 0:
return False
number_test -= 1;
return True
if __name__ == '__main__':
euler37lib.main(is_prime)
Comparativa de rendimiento
Usando librería:
Implementación "refinada"
Nuestra implementación "refinada" tiene tiempos comparables a la implementación usando el módulo
sympy.
Implementación mala:
Esta otra pasa de apenas un segundo de las anteriores a 9 minutos. Es 540 veces más lenta.
Implementación inservible:
5.100 segundos. Las dos primeras implementaciones tardaban como 1 segundo. Un algoritmo 5.000 veces más lento.
Conclusiones
- Los algoritmos sí que importan. Si este programa, por ejemplo, fuese código para producción, ninguna de las dos implementaciones sencillas sería aceptable.
- Con matices: si en el problema se nos garanzizase que, por ejemplo, siempre tendremos datos de entrada con números por debajo de 100, no hay ninguna mejora apreciable en el rendimiento por usar una u otra versión de is_prime().
- Si existe una librería o módulo que hace lo que necesitas y es de pago, cómpralo o convence a tu jefe/cliente para que lo compre [*]:
- Funcionará mejor.
- Tendrá soporte.
- A la larga será más económico.
[*] Es una generalización un poco burda, tampoco vamos a estar metiendo librerías o código de terceros para todo, pero es un poco la idea: los "vendor" suelen hacer las cosas mejor que lo que tú puedas hacer.