Obtención de la lista de divisores

Algoritmo con hoja de cálculo

(Si no te interesa la programación en Basic puedes dejar de leer)

Para encontrar los divisores de un número N la búsqueda más simple consiste (salvo alguna pequeña modificación que la acelere) en recorrer todos los números menores o iguales a N y tomar nota de los que son divisores suyos. Es muy sencilla de programar y sólo ocupa unas pocas líneas de código. Tiene el inconveniente de que para números de más de cuatro o cinco cifras decimales resulta muy lenta en hoja de cálculo, que es la herramienta que usamos en este blog.

Un algoritmo más rápido consiste en reproducir en la hoja el esquema que siempre se ha usado en las clases de Matemáticas, el que desarrolla las distintas potencias del primer divisor primo y después las combina con las de los demás en una tabla bidimensional como la siguiente, que se corresponde con los divisores del número 33075=3³*5²*7²


3        1          3          9          27
5        5        15         45        135
        25        75       225        675
7        7        21         63        189
        35      105       315        945
       175     525     1575      4725
        49     147        441      1323
       245    735      2205      6615
     1225    3675   11025    33075


En ella se han situado en la primera columna los factores primos, en la primera fila las potencias del 3 y en las demás filas los distintos productos que se pueden formar entre las potencias, sumandos formados en la fórmula

de la obtención de sigma(N).

Para poder construir este esquema en la hoja necesitamos saber qué factores primos posee el número y con qué exponentes. La siguiente subrutina en Basic nos los proporciona:

Global p(50) as long  Se definen las variables p para los factores, e los exponentes y np el número total
Global e(50) as integer
Global np%



Sub sacaprimos(a)
Dim f,i
dim vale as boolean


f=2:i=1:e(i)=0:vale=false:np=0
while f<=a  El bucle while_wend divide el número entre el factor todas las veces posibles
if esprimo(f) then
while a/f=int(a/f)  Es divisor primo
vale=true
p(i)=f
e(i)=e(i)+1  aumenta el exponente
a=a/f
wend
if vale then
np=np+1  aumenta el número de factores
i=i+1:e(i)=0 se inicia un nuevo exponente
end if
vale=false
end if
f=f+1 buscamos otro factor primo
wend
End sub

Con este código obtenemos la lista de factores primos p(i), la de exponentes e(i) y el número total de factores primos np.

Al usar estos datos la búsqueda de divisores se simplifica mucho, pues todo el trabajo consistirá ahora en construir la tabla que estudiamos en nuestros años escolares:

(a) Formamos una fila con las potencias posibles del primer factor primo. Tomamos nota de que la altura de la tabla es de 1. También recogeremos el dato de la variable fila en la que se han escrito.

(b) Vamos multiplicando esas potencias de la primera fila por todas las de los otros primos, pero teniendo cuidado de:

* En cada nuevo primo la altura queda multiplicada por e(i)+1, que es el número de sus potencias posibles.

* En cada nuevo producto deberemos incrementar la variable fila en una unidad, para que se vaya formando la tabla hacia abajo.

* Deberemos usar muchos bucles anidados, porque intervienen as variables del número de potencias de la primera fila, el de las del resto de primos y las del número de primos diferentes.

Un posible código en OpenOffice sería:

sub todosdivisores


dim i,j,k,l, altura,fila
dim divi as long


Rellena la primera fila con las potencias del primer primo
if np>=1 then
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,11).value=p(1)
for k=0 to e(1)
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+k,11).value=p(1)^k
next k
end if


Va multiplicando las potencias de los demás primos
if np>=2 then
altura=1:fila=12
for k=2 to np  Este bucle recorre los primos
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,fila).value=p(k)
for j=1 to e(k)  Recorre las potencias del primo actual
for i=1 to altura Recorre todos los divisores anteriores
for l=0 to e(1)  Ídem los elementos de cada fila
divi=StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,10+i).value
divi=divi*p(k)^j  Efectúa el producto y lo escribe
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,fila).value=divi
next l
fila=fila+1  Una vez escritos, aumenta la fila
next i
next j
altura=altura*(e(k)+1)  La altura se amplía
next k
end if
end sub

Pues ya tienes una idea. El resto es cosa tuya. Seguro que la mejoras.