Coste de un algoritmo

Un algoritmo es el conjunto de operaciones y procedimientos que deben seguirse para resolver un problema.
En la entrada anterior sobre: ¿Cuántos números primos hay?, proponíamos una forma de averiguar si un número es o no primo, averiguando los divisores que tiene. Por ejemplo para saber si 5877 es primo, hacemos las divisiones por 1, 2, 3, 4, 5, ...5877. de esta manera sabremos cuántos divisores tiene y por tanto si es primo o no.
A medida que el número crece el tiempo invertido en averiguar si es primo o no es mayor.

Supongamos que en una división invertimos 1 segundo. Para averiguar si 5877 es primo según el algoritmo anterior emplearíamos 5877 segundos=97,95 minutos=1,63 horas

Para averiguar saber los divisores que tiene 1.000.000, emplearíamos:
1.000.000 segundos =16.666minutos =277horas =11,5 días.

Habrá números que necesitemos más de 100 años, otros más de 1000 años, e incluso habrá números que necesitemos más de 15.ooo millones de años que es la edad estimada del universo.

Costaría mucho tiempo averiguar el número de divisores que tiene un número.

¿Hay otro algoritmo mejor para conocer los divisores de un número?

Esta pregunta es fundamental en programación de ordenadores. ¿Cómo mejorar un algoritmo? es decir, ¿Cómo reducir el tiempo en la resolución de un problema?

Una forma de mejorar el algoritmo de averiguar los divisores de un número, es realizando las divisiones hasta la raiz cuadrada del número: si a un número se le conoce un divisor, se puede averiguar otro divisor asociado sin mas que dividir. Por ejemplo: 9 divide a 36 el asociado a 9 es 4, ya que 36=9.4
Si un divisor es menor que la raiz cuadrada el asociado será mayor. Averiguando los menores o iguales que la raiz sabremos los mayores.
En este nuevo algoritmo el coste será en tiempo la raiz cuadrada.
Para 1.000.000 emplearíamos raiz(1.000.000)=1.000 seg =16,67 minutos y no 11,5 días.