<< Divisor común mayor factorizando >>

Dificultad:

Lecciones anteriores:

Los Primos

Divisor común mayor En esta lección se explica la idea del DCM y se ven algunos programas que permiten comparar los distintos algoritmos para camcular el DCM.

Resumen:

Vamos a calcular el divisor común mayor entre dos números mirando sus correspondientes factorizaciones en primos. Se deben buscar los primos que aparecen en la factorización de ambos y tomar el menor exponente. Por ejemplo:

DCM(700, 150) = DCM(2²*5²*7¹ ,2¹*3¹*5²) = 2¹*5² = 50

Repaso:

En la lección anterior comenzamos a analizar varios métodos para calcular el Divisor Común Mayor entre dos números tanteando todos los posibles divisores, o casi.

También apareció un probador de funciones que calcula el DCM de muchos numeros elegidos al azar y mide cuánto tiempo tarda. Así es posible comparar los distintos métodos.

Factorizando:

El cálculo del DCM entre dos números es más sencillo de programar si vamos factorizando ambos números simultáneamente. Al mismo tiempo vamos calculando el DCM multiplicando los factores que vayamos encontrando. (En todos lados suponemos que a y b son enteros positivos.)

Deflng A-Z
Function DCMFactoriza(a,b) 
  CopiaA=a 'Copia a A (ver nota mas abajo)
  CopiaB=b 'Copia a B (ver nota mas abajo)
  Resultado=1
  PrimoActual=2
  Do 
    'Busco la mayor potencia de PrimoActual
    'que divide a CopiaA
    PotenciaA=0
    Do While CopiaA Mod PrimoActual =0
      PotenciaA=PotenciaA+1
      CopiaA=CopiaA\PrimoActual
    Loop
    
    'Busco la mayor potencia de PrimoActual
    'que divide a CopiaB
    PotenciaB=0
    Do While CopiaB Mod PrimoActual =0
      PotenciaB=PotenciaB+1
      CopiaB=CopiaB\PrimoActual
    Loop
    
    'Elijo la menor potencia
    If PotenciaA<=PotnciaB Then
      Resultado=Resultado*PrimoActual^PotenciaA
    Else
      Resultado=Resultado*PrimoActual^PotenciaB
    Endif
  Loop Until CopiaA=1 Or CopiaB=1
  DCMFactoriza=Resultado
End Function

El programa sigue hasta que alguno de los dos números (CopiaA o CopiaB) llega a 1. También se puede esperar a que los dos sean 1 (reemplazando el Or por un And) pero tarda mas y da lo mismo.

Sería interesante arreglar un poco esta función para que tenga en cuenta que si PrimoActual es mayor que la raíz cuadrada de CopiaA (o CopiaB) entonces CopiaA (o CopiaB) es un primo y es inútil que siga tratando de factorizando.

Otra posibilidad es usar algunas propiedades del DCM:

• si a y b son múltiplos de d entonces
  DCM(a,b) = d * DCM(a/d,b/d)
• si a es múltiplo de d y b no tiene factores comunes con d entonces
  DCM(a,b) = DCM(a/d,b)

Esto ayuda a calcular el DCM a ojito, bueno en realidad se usan algunas reglas de divisibilidad que son fáciles de ver. Por ejemplo calcular DCM( 113300, 39390) sin calculadora (o casi).

Como 113300 y 39390 son múltiplos de 10, entonces puedo calcular el DCM entre 11330 y 3939 y multiplicarlo por 10. Ahora, como 11330 es múltiplo de 10 y 3939 no tiene factores primos en común entonces da lo mismo calcular el DCM entre 11330 y 3939 que el DCM entre 1133 y 3939. Bueno, sigo así un rato y queda ...

DCM(11330*10,3939*10) =10*DCM(11330,3939) =10*DCM(1133*10,3939) =10*DCM(1133,3939) =10*DCM(1133,1313*3) =10*DCM(1133,1313) =10*DCM(1133,101*13) =10*DCM(1133,101) =10*DCM(11*103,101) =10*DCM(103,101)=10*1 ( me fijé en la tabla que 101 y 103 son primos) =10

Con estas reglas se puede escribir la siguiente función.

Deflng A-Z 
Function DCMFactorizaDeAUno(a,b) 
  CopiaA=a 'Copia a A (ver nota mas abajo)
  CopiaB=b 'Copia a B (ver nota mas abajo)
  Resultado=1
  PrimoActual=2
  Do
    If CopiaA Mod PrimoActual =0 Then
      If CopiaB Mod PrimoActual =0 Then
        'Los dos son multiplos!
        CopiaA=CopiaA\PrimoActual
        CopiaB=CopiaB\PrimoActual
        Resultado=Resultado*PrimoActual
      Else
        'CopiaA es multiplo pero CopiaB no
        CopiaA=CopiaA\PrimoActual
      EndIf
    Else
      If CopiaB Mod PrimoActual =0 Then
        'Solo CopiaB es multiplo
         CopiaB=CopiaB\PrimoActual
      Else
        'Ninguno es multiplo
        'paso al siguiente primo
        PrimoActual=PrimoActual+1
      EndIf
    Endif
  Loop Until CopiaA=1 Or CopiaB=1
  DCMFactorizaDeAUno=Resultado
End Function

Al comparar el tiempo que tarda esta función se ve que es mucho más rápida que las anteriores, sobre todo si los números tienen varios factores primos chiquitos (por ejemplo calculando DCM(14929920, 170859375) ).

También habría que modificar esta función para que deje de buscar al llegar a una de las raíces cuadradas, de la misma manera que dejabamos de buscar divisores para ver si un numero es primo en una lección anterior. Sino esta función puede ser muy lenta si los números llegan a ser primos grandes. Sobre todo si uno quiere usarla en un problema pesadito (ej: calcular el DCM de los siguientes 10⁶ pares de números : (23234352,2354663);(57446872;665682323);....)

Notas:

Nota 1: En ambos programas PrimoActual toma todos los valores empezando de 2. Lo ideal sería que saltara de un primo al siguiente. Esto es dificil de programar. Tampoco es conveniente revisar si PrimoActual es un primo o no, porque uno tarda más tiempo revisando eso que haciendo las divisiones. Sin embargo, por las propiedades de los primos, cada vez que PrimoActual divide a CopiaA o CopiaB el valor que tiene es un número primo (de verdad).

Nota 2: En ambos programas se hacen copias de los parámetros a y b para operar con las copias y no modificarlos. Esto es necesario porque sino al cambiarse los valores dentro de la función, se cambian los valores de las variables en el programa principal (o de donde se llame a la función). Esto sólo es necesario en QB y VB, pero no en Pascal, C, etc. porque en estos lenguajes la función recibe normalmente sólo el valor de las variables. En general uno ni se preocupa por todo esto, hasta que el programa comienza a hacer cosas inexplicables. Si querés leer un poco más sobre este tema y ver otros ejemplo podes ir a esta página

Ejercicios:

1. ¿Cuál es el primo más grande que entra en un entero largo? ¿Cuál es el segundo? ¿Tarda mucho en calcular el DCM entre estos dos números? ¿Como varía el tiempo que tarda la función si se le pide calcular el DCM entre los números que se obtienen al sumarle 1 a cada uno de estos primos?
   
2. ¿El divisor común mayor entre dos cuadrados perfectos es un cuadrado perfecto? Probar un rato con la computadora y después demostrarlo. (Nota los cuadrados perfectos son 1=1², 4=2², 9=3², 16=4², ...)
   
3. Comparar las dos funciones (arregladas) para ver cuál va más rápido. Compararlas con las de las lecciones anteriores. (Ver Probador de funciones)
   
4. Se escriben en dos columnas los primeros 23 números de Fibonacci, el primero en la izquierda, el segundo en la derecha, el tercero en la izquierda, el cuarto en la derecha y así sucesivamente. Calcula el divisor común mayor entre el producto de todos los de la columna izquierda y el producto de todos los de la columna derecha.
   Los números de Fibonacci se definen de la siguiente manera:
   F₁ = 1
   F₂ = 1
   F_n+2 = F_n+1 + F_n
   Por ejemplo F₃=2, F₄=5_, F₅=8,...
   

Lecciones siguientes:

Algoritmo de Euclides