Listas

15. Ejercicios Resueltos

15.12. Fibonaccio 2 de 3

Un alumno, luego de la clase de bucles y el ejemplo de Fibonacci, plantea el siguiente problema:

"Encontrar los primeros 10 números primos de la serie de Fibonacci."

Una posible solución, bastante eficiente, sería la siguiente:

# ------------------------------------------------------------------------ #
# Semilla inicial, evitamos arrancar con 0 y 1, ya que 1 no es primo

a, b = 1, 1

# Lista para guardar los primos hallados

primos = []

while True:

# PARTE PARA FIBONACCI

# C es el valor actual bajo análisis

# Como 1 no se considera primo, se comienza desde el siguiente

c=a+b

a, b = b, c # Actualizo semilla para la próxima iteración

# PARTE PARA PRIMOS

# El límite para la búsqueda de divisores es raiz cuadrada de C

# Si hasta ese punto no existe un divisor distinto de 1 o sí mismo,

# el número es primo. Es un teorema fácilmente demostrable

esPrimo = True

for i in range(2,int(c**(1/2))+1):

if c%i == 0:

esPrimo = False

# Si existe un divisor, deja de ser primo.

# Interrumpo el análisis del número

break

if esPrimo:

primos.append(c)

if len(primos) == 10:

# Finaliza el while cuando encuentro los 10 primos

break

print(primos)
# ------------------------------------------------------------------------ #

Notar que en este tipo de problemas, es crucial evitar iteraciones innecesarias, ya que, de ser así, el tiempo necesario para hallar la solución incrementa considerablemente (el décimo primo es bastante grande). El ejemplo es especial para repasar o entender el concepto de "código eficiente". Verificar los tiempos de demora respecto a un código implementado por otra persona, que no haya visto la solución obviamente :) .

Al ejecutar este código, se obtiene la siguiente lista:

[2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437]

Para terminar de comprender qué es eso de "código eficiente", a continuación, se dejar un script con varias modificaciones al algoritmo. Permitiendo observar la diferencia en cuánto al tiempo de ejecución que requiere cada uno para llegar al mismo resultado. Lo pueden probar en sus propias máquinas.

SCRIPT

NOTA: En el Script pueden modificar la variable "primos_buscar", a fines de indicar cuántos primos se quieren de la serie de Fibonacci. Lo dejo así para darle versatilidad a la prueba y que ajusten el parámetro en base a las características de su PC. Con 9 primos debería ir bien. De ahí en más... la Variante 3 cada vez demorará más (que es la que demora mucho en un principio, ahora se explica qué es esto. En realidad, cualquiera de las variantes comienzan a demorar más, pero esta es la peor de todas).

Al ejecutar el script, podrán ver algo similar a lo siguiente:

# CASO A: 9 primeros primos

Como se aprecia en la figura, los tiempos crecen con cada variante. La Variante 1 corresponde al código optimizado. La Variante 2 tiene comentado el break que ahorra ciclos en el for que busca divisores. La Variante 3 considera para la búsqueda de divisores, hasta el valor del número que se está comprobando. En los 2 primeros casos, el tiempo de demora es tan pequeño que el programa lo redondea a 0 segundos, puede verse que la cantidad de ciclos se duplica de todas maneras. El último caso demora 240 milisegundos aproximadamente, y la cantidad de ciclos crece abismalmente.

# CASO B: 10 primeros primos

Al querer buscar 1 primo más, los tiempos y ciclos crecen exponencialmente. Los tiempos dependen de cada PC, pero la cantidad de ciclos será la misma.

Notar que la Variante 1 (la optimizada), demora casi 4 milisegundos en hallar la solución. La Variante 2 demora 21 milisegundos, mientas que la Variante 3 un total de 214 segundos. Los cambios en el código son ínfimos, pero la diferencia es notable. Estos tiempos se justifican con la cantidad de ciclos que se cumplen en los bucles, para hallar los valores buscados. Notar que en la última variante, el número de ciclos es totalmente exagerado, así como el tiempo que demora (en comparación a las variantes anteriores).

Con un número bajo de primos a hallar, no se nota tanto la diferencia en cuánto a la eficiencia. Pero al necesitar procesar un volumen considerable de cálculos, es ahí cuando destaca un buen algoritmo, un código eficiente.

NOTA: El código inicial puede aún ser mejorado en gran medida, aquí se presentaron algunos conceptos a fines de que pueda inspirarse para lograrlo 😆.