Dificultad:

Se necesitan conocimientos elementales de computación y de matemática.

Lecciones anteriores:

Los Primos (más o menos)

Resumen:

En esta lección vamos a comenzar a ver algunos métodos para calcular el Divisor Común Mayor (DCM) entre dos números, o sea el mayor entero que los divide a ambos.

Introducción:

Para cada método vamos a definir una función que devuelve el DCM entre sus dos parámetros. Los nombres de estas funciones serán DCMAlgo, por ejemplo DCMTodos, DCMRaiz,... .

Sería interesante que trates de escribir una función que calcule el DCM (por ejemplo DCMYo) antes de seguir leyendo. La forma de las funciones va a ser como la siguiente. Tiene dos parámetros que son números enteros. Después hace algunas cuentas (que no están en este ejemplo). Y al final devuelve un número entero que es (esperamos) el DCM.

Deflng A-Z 'Todas las variables son enteros largos
Function DCMYo(a,b)
    'Aca hago una cuenta interesante
    '...
    DCMYo=ElResultado
End Function

Tenemos un par de ejemplos para usar estas funciones.

• En Usando las funciones DCM hay un programa para ver cómo andan estas funciones. Pregunta dos números, calcula su DCM con una de estas funciones y después muestra el resultado en la pantalla.
• En Probador de funciones DCM hay un programa para ver cuáles de estas funciones andan más rápido. Elije muchos pares de números al azar y les calcula el DCM. Al final muestra cuánto tardo en hacer todas estas cuentas.

Estos ejemplos vienen con una función que calcula el DCM, pero que es lenta. La idea es que la reemplacen por alguna de las que aparece acá o en las lecciones siguientes.

(Para evitar deltalles técnicos vamos a suponer que los dos números son positivos, más adelante analizaremos los casos en que son cero o negativos.)

Mirando a todos:

La primera posibilidad es calcular todos los divisores de a y todos los de b y luego compararlos. El problema es que hay que guardarlos en algún lado, por lo que es más difícil. Una solución más sencilla consiste en probar con todos los números y ver si dividen a ambos. La siguiente función utiliza este método, pero antes elige el menor entre a y b(¿Por qué?).

Deflng A-Z 'Todas las variables son enteros largos
Function DCMTodos(a,b)
    'Busco el menor
    If a<b Then
        min=a
    Else
        min=b
    EndIf
    
    For d=1 To min
        If (a Mod d=0) And (b Mod d=0) Then
            MayorDivisorHastaAhora=d'
        EndIf
    Next i
    DCMTodos=MayorDivisorHastaAhora 'Como resultado manda el mejor que encontró
End Function

Para que sea más rápido (mucho más rápido) se utilizó modulo, que solo hace cuentas con enteros. Si no conocés este operador mirá la ayuda o leé está página.

Divisores:

En la lección sobre primos vimos que por algunas propiedades de los divisores, no hacía falta probar con todos los números, sino que alcanzaba con probar hasta la raíz cuadrada. Con un truco parecido vamos a poder mejorar bastante el programa. Antes que nada vamos a escribir un programa que imprime todos los divisores de un número.

Deflng A-Z 'Todas las variables son enteros largos
Cls
Do
    Input "N=",n
    If n=0 Then End 'Termina el programa si n es cero
    For d=1 To n
        If n Mod d=0 Then
            Print d, n/d
        EndIf
    Next
Loop

Para cada valor de n deberían aparecer dos columnas, en la primera aparecen todos los divisores y en la segunda el resultado de dividir a n por el divisor. Por ejemplo:

N=60
1    60
2    30
3    20
4    15
5    12
6    10
10   6
12   5
15   4
20   3
30   2
60   1

Al dividir un número por un divisor también se obtiene un entero (¡por la misma definición de divisor!). Así que en la segunda columna figuran todos los divisores pero en el orden inverso, de mayor a menor. Lo interesante es calcular hasta que valor la columna de la izquierda es mayor que la de la derecha.

Veamos primero un casos especial. Si llamamos d=n y es justo un divisor de n entonces n/d es el mismo número. Por ejemplo si

N=36
1    36
2    18
3    12
4    9
6    6
9    4
12   3
18   2
36   1

En la primera columna están antes del 6 todos los divisores más chicos y en la segunda están antes que el 6 todos los más grandes. Así que si quiero los divisores en cualquier orden puedo simplemente probar hasta el 6 en este caso y cortar el programa. La ventaja es que tengo que hacer muchas menos divisiones, en este caso sólo 6 (que se podrían hacer a mano) en vez de 36 (que ya no dan ganas). Esto es mucho más útil cuando N es grande por ejemplo N=10000, ya que en vez de 10000 cuentas hago sólo 100, con el correspondiente ahorro de tiempo.

El caso general es completamente análogo. Si prueba con todos los números hasta la raíz cuadrada, me aparecen todos los divisores.

• Si d es un divisor de n que es menor que n entonces aparecerá en la primera columna.
• Si d es un divisor de n que es mayor que n entonces n/d es menor que n, así que aparecerá en la segunda columna.
• Si n es divisor de n entonces aparece en las dos, por lo que hay que tener un poco de cuidado.

Ahora vamos a calcular el DCM utilizando esta propiedad. La idea es que si es divisor de ambos entonces seguro que es divisor del más chico. Entonces buscamos todos sus divisores y nos fijamos si dividen al otro. Si además es más grande que todos los que habíamos encontrado lo anotamos en MayorDivisorHastaAhora.

Deflng A-Z 'Todas las variables son enteros largos
Function DCMRaiz(a,b)
    'Busco maximo y minimo
    If a<b Then
        min=a
        max=b
    Else
        min=b
        max=a
    EndIf
    'Ahora busco el DCM
    MayorDivisorHastaAhora=-1
    'cualquiera que encuentre va a ser mayor
    For d=1 To Sqr(min)
        If min Mod d=0 Then
            ' d es divisor de min
            If max Mod d=0 Then
                If MayorDivisorHastaAhora<d Then
                    MayorDivisorHastaAhora=d
                Endif
            Endif
            e=min\d ' min/d tambien es divisor de min
            If max Mod e=0 Then
                If MayorDivisorHastaAhora<e Then
                    MayorDivisorHastaAhora=e
                Endif
            Endif
        EndIf
    Next i
    DCMRaiz=MayorDivisorHastaAhora
    'Como resultado manda el mejor que encontró
End Function

(¿Qué pasa si justo la raíz cuadrada de min es entera? ¿Por qué no hay ningún problema?)

Se puede mejorar ligeramente esta función teniendo en cuenta el orden en que aparecen los divisores. Por ejemplo si algún e divide a max cualquier otro divisor que uno encuentre después va a ser más chico (¿por qué?), por lo que la función puede dejar de probar en ese punto. Además después de esta modificación los divisores que se obtienen son los que figuran como d por lo que no hace falta fijarse si el MayorDivisorHastaAhora es menor(¿por qué?). Hacer una función DCMRaizMejor con estos cambios y corregirla hasta que se obtengan los mismos resultados que con DCMRaiz .

Ejercicios:

1. Calcular la suma de la cantidad de divisores de los números del 1 al 100000. (Ojo con los cuadrados, probar con 100 en vez de 1000000). Comparar cuanto tarda el programa que prueba con todos los números y el que utiliza el sistema de la raíz cuadrada.
   
   
2. Encontrar todos los números N tales que el producto de todos sus divisores no es una potencia de N(Por ejemplo si N=10 entonces 1*2*5*10=10²,pero si N=4 entonces 1*2*4 no es una potencia de 4) (Sugerencia: hacer un programa que pruebe hasta que te aburras, mirar la lista de valores, tratar de encontrar una relación y demostrar que realmente vale lo que se ve a ojo.)
   
   
3. Modificar la función DCMTodos para que pruebe si d es un divisor en orden decreciente desde min hasta 1. ¿Cambia mucho el tiempo de ejecución? (Ver Probador de funciones)
   
   
4. Calcular el divisor común mayor de todos los números de seis cifras tales que la suma de sus cifras es 24.

Lecciones siguientes:

Divisor Común Mayor Factorizando

Algoritmo de Euclides