Clase Pii - Cambio De Base.docx

Algoritmo de Euclides El algoritmo de Euclides sirve para obtener el máximo común divisor (abreviado normalmente como M.C.D.) de dos números enteros positivos. El mínimo común múltiplo (M.C.M.), puede obtenerse también con éste algoritmo, haciendo una sencilla operación con el M.C.D. obtenido. Se llama así por Euclides de Alejandría, un matemático griego que vivió en los tiempos del faraón Ptolomeo I, del que nos han quedado algunos textos recopilatorios del saber matemático y geométrico de su época. No es que Euclides escribiera tal cual éste algoritmo, sino que, aparentemente, dejó escritas algunas relaciones entre números que son la base de lo que hoy llamamos MCD. Es uno de los algoritmos típicos que los profesores de programación ponen a sus alumnos para practicar el bucle repetir-mientras o hacer-hasta (repeat-until o do-while) pasando valores de una iteración a otra del bucle.

Máximo Común Divisor (MCD) El máximo común divisor de dos números enteros positivos a y b es otro número entero positivo c tal que si dividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta caracterísitica. Como nos decían en el "cole", el máximo común dívisor (mcd) de dos enteros a y b es el mayor entero c que divide exactamente a a y b. Aunque en el colegio nos enseñan a encontrar el mcd a partir de la descomposición en factores primos de a y b, esa no es una buena forma de obtener el mcd computacionalmente, ya que el algoritmo para descomponer en factores primos es muy costoso, en términos de computación. El algoritmo de Euclides es bastante más eficiente para obtener el mcd, aunque normalmente sorprende un poco cuando tenemos contacto con él por primera vez. El algoritmo de Euclides es el siguiente: Algoritmo de Euclides Siendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo que obtendremos un resto r1 y un cociente q1. Hacemos la operación q1=a/b, utilizando la división entera, sin decimales.... pero realmente no sólo nos interesa el resultado o cociente de la división, sino que nos interesa también el resto, así que la operación la vamos a reescribir de otra forma. Es importante que llamemos "a" al mayor de los dos números (siempre el mayor va a ser a). Debemos dividir a entre b y obtener un cociente (al que llamaremos q1) y un resto (al que llamaremos r1). Obtenidos ese cociente y ese resto, se cumple que: a=q1·b+r1 Los lenguajes de programación suelen tener un operador para efectuar la división entera (con lo que obtendremos q1. Por ejemplo, en C#: "q1=a/b;"), y otro para obtener el resto o módulo de la división (con lo que obtendremos r1. Por ejemplo, en C#: "r1=a%b;"). A partir de esa primera división, es necesario repetir un proceso:  dividir el numero que fue divisor en el paso anterior entre el resto obtenido en el paso anterior  despreciar el cociente  si el resto obtenido esta vez es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.  Si el resto no es 0, ir al primer paso Es un poco engorroso la primera vez, pero realmente es un algoritmo muy sencillo. Siguiendo con el ejemplo, en la segunda iteración, dividiríamos b/r1 obteniendo un resto r2 (hacemos la operación de división para obtener el cociente, al que llamamos q2 y la de obtener el resto, al que llamamos r2), de tal manera que se cumpliría lo siguiente: b=q2·r1+r2 En la tercera iteración, dividimos r1/r2 obteniendo un resto r3 r1=q3·r2+r3 Y se continúa así hasta obtener un resto 0. El último resto (llamémosle rk) distinto de cero es el mcd. rk-2=qk·rk-1+rk rk-1=qk+1·rk+0 rk es el mcd(a,b) Es decir, empezamos dividiendo un número entre otro (obteniendo el resto también, no sólo el cociente), y a partir de ahí, seguimos dividiendo el número más pequeño entre el resto que nos ha salido... y continuamos 1 / 11

dividiendo por el resto anterior una vez y otra hasta que en ese proceso repetitivo obtengamos un resto que sea 0. ¡Ya lo tenemos!. El mcd es es resto anterior (que no es cero). Como comentábamos al principio, es muy sencillo implementarlo iterativamente. Basta tener en cuenta que en cada vuelta del bucle, y siempre a partir de la segunda iteración hay que hacer que el divisor sea el resto de la iteración anterior y el dividendo sea el divisor de la iteración anterior. Vamos a hablar de código utilizando C#. En el código que construiremos vamos a utilizar dos variables enteras i1 e i2, que inicialmente van a contener los valores de los dos enteros a y b que se pasen como parámetros, de tal manera que i1 tendrá al mayor de los dos, e i2 al más pequeño... y a partir de ahí nos metemos en un bucle. La dinámica es siempre la misma: obtenemos el resto de la división, y si no es 0, debemos hacer otra repetición. Pero antes de la siguiente repetición, desplazamos los valores: lo que contenía i1 ya no nos sirve. Metemos en i1 lo que tiene i2, y en i2 el resto que hemos obtenido.... El algoritmo de euclides en C# 1 static int EuclidesMCD(int a, int b) { 2 int iaux; //auxiliar 3 a = Math.Abs(a); //tomamos valor absoluto 4 b = Math.Abs(b); 5 int i1=Math.Max(a,b); //i1 = el más grande 6 int i2=Math.Min(a,b); //i2 = el más pequeño 7 do{ 8 iaux = i2; //guardar divisor 9 i2 = i1 % i2; //resto pasa a divisor 10 i1 = iaux; //divisor pasa a dividendo 11 } while (i2 != 0); 12 return i1; //ultimo resto no nulo 13 } Al principio cuesta un poco de coger... te recomiendo hacer una traza mentalmente (o mejor, ayudándote de papel). Te darás cuenta de cómo se van "desplazando los valores" a medida que vamos dividiendo hasta obtener el resto 0... aunque, realmente... no estamos utilizando los cocientes, sino sólo los restos ;-) Aunque en la introducción hemos mencionado la división ("/"), realmente no es del todo cierto... sólo queremos los restos, no el cociente...(operador módulo o resto: "%" en C#). Hemos introducido esta pequeña mentira en la explicación (pero no en el código) porque cuando dividimos "a mano", realmente en la misma operación de división obtenemos dos resultados a la vez: por un lado el cociente y por otro, el resto. Sin embargo, los lenguajes de programación hacen cada una de esas cosas por separado: pueden obtener un cociente sin necesidad de obtener un resto y al revés, obtener un resto sin necesidad de dividir... así que en nuestro algoritmo no dividimos realmente: sólo obtenemos el resto. Si lo hiciéramos "a mano", tendríamos que dividir, con lo que obtendríamos el cociente y el resto simultáneamente, pero despreciaríamos el cociente y nos quedaríamos sólo con el resto. Mínimo Común Múltiplo. (MCM) Muy relacionado con el máximo común divisor está el mínimo común múltiplo (mcm). El mcm de dos enteros positivos a y b es un valor c entero y positivo tal que al dividir c/a y c/b el resto es 0, y además no existe otro número menor que c que cumpla esta condición. Hay una relación muy sencilla entre mcm y mcd. Es ésta: mcm(a,b)=(a·b)/mcd(a,b) Así pues, también podemos obtener el mcm mediante el algoritmo de Euclides. Obtener el MCM con el algoritmo de Euclides, en C# 1 static int EuclidesMCM(int a, int b){ 2 return (a / EuclidesMCD(a, b)) * b; 3 } NOTA Observa que primero se divide a entre el mcd, en lugar de multiplicar a*b. Esto se hace para evitar un posible desbordamiento al multiplicar a*b. Ejemplo

2 / 11

Máximo común divisor: el máximo común divisor, m.c.d. de dos o más números es el mayor número que divide a todos exactamente. Cálculo del máximo común divisor:  Se descomponen los números en factores primos.  Se toman los factores comunes con menor exponente. Hallar el m. c. d. de: 72, 108 y 60.

m. c. d. (72, 108, 60) = 22 · 3 = 12 12 es el mayor número que divide a 72, 108 y 60. Si un número es divisor de otro, entonces éste es el m. c. d. El número 12 es divisor de 36. m. c. d. (12, 36) = 12 Mínimo común múltiplo Es el menor de todos múltiplos comunes a varios números, excluido el cero. Cálculo del mínimo común múltiplo 1. Se descomponen los números en factores primos 2. Se toman los factores comunes y no comunes con mayor exponente. Ejemplo  72 = 23 · 32  108 = 22 · 33  60 = 22 · 3 · 5 m. c. m. (72, 108, 60) = 23 · 33 · 5 = 1 080 2160 es el menor número que puede ser dividido por: 72, 108 y 60. Si un número es un múltiplo de otro, entonces es el m. c. m. de ambos.  El número 36 es múltiplo de 12.  m. c. m. (12, 36) = 36 Relación entre el m. c. d. y m. c. m. m. c. d. (a, b) · m. c. m. (a, b) = a · b Ejercicios 1. Calcular el m. c. d. y m.c.m. de:  1428 y 376 428 = 22 · 107 376 = 23 · 47 m. c. d. (428, 376) = 22 = 4 m. c. m. (428, 376) = 23 · 107 · 47 = 40 232 

2148 y 156 148 = 22 · 37 156 = 22 · 3 · 13 m. c. d. (148 , 156) = 22 = 4 m. c. m. (148 , 156) = 22 · 3 · 37 · 13 = 5772



3600 y 1 000 600 = 23 · 3 · 52 3 / 11

1000 = 23 · 53 m. c. d. (600 , 1000) = 23 · 52 = 200 m. c. m. ( 600 , 1000) = 23 · 3 · 53 = 3000 2. Calcular el m. c. d. y m.c.m. de:  11048, 786 y 3930

1048 = 23 · 131 786 = 2 · 3 · 131 3930 = 2 · 3 · 5 · 131 m. c. d. (1048, 786, 3930) = 2 ·131 = 262 m. c. m. (1048, 786, 3930) = 23 · 3 · 5 · 131 = 15 720 

23120, 6200 y 1864

3210 = 24 · 3 · 5 · 13 6200 = 23 · 52 · 31 1864 = 23 · 233 m. c. d. (3210, 6200, 1864) = 23 = 8 m. c. m. (3210, 6200, 1864) = 24 ·3 · 52 · 13 · 31 · 233 = 112 678 800 3. Un faro se enciende cada 12 segundos, otro cada 18 segundos y un tercero cada minuto. A las 6.30 de la tarde los tres coinciden. Averigua las veces que volverán a coincidir en los cinco minutos siguientes. 12 = 22 · 3 18 = 2· 32 60 = 22 · 3 · 5 m. c. m. (12 , 18, 60) = 22 · 32 · 5 = 180 180 : 60 = 3 Sólo a las 6.33 h. 4. Un viajero va a Barcelona cada 18 días y otro cada 24 días. Hoy han estado los dos en Barcelona. ¿Dentro de cuantos días volverán a estar los dos a la vez en Barcelona? 18 = 2 · 32 24 = 23 · 3 m. c. m. (18, 24) =23 · 32 = 72 Dentro de 72 días. 5. ¿Cuál es el menor número que al dividirlo separadamente por 15, 20, 36 y 48 en cada caso dar de resto 9? m. c. m. (15 , 20, 36, 48) = 24 · 32 · 5 = 720 720 + 9 = 729

4 / 11

Cambio de base 10 a otras bases Para transformar un número de base decimal a otra base: se divide por esta base tantas veces como sea necesario hasta obtener un resto menor que la base; después, se anotan como numerales el último cociente y, en orden inverso, los sucesivos restos obtenidos. Veamos ejemplos: 1) Pasar el número 65 a código binario

2) Convertir el número 65 a base 3

Conversión a base decimal Para pasar un número de una base cualquiera a la decimal, se recurre a la forma polinómica. Por ejemplo: 1) Pasar el número 3415 de base 5 al sistema decimal

2) Pasar el número binario 110101 al sistema decimal

5 / 11

CONVERSIÓN DE UN SISTEMA NUMÉRICO A OTRO Matemáticamente, existe la posibilidad de convertir un número de un sistema numérico a otro. Descomposición en factores de un número base 2 (binario) y su conversión a un número equivalente en el sistema numérico decimal. Veamos ahora cómo llevamos el número binario 101111012 a su equivalente en el sistema numérico decimal. Para descomponerlo en factores será necesario utilizar el 2, correspondiente a su base numérica y elevarlo a la potencia que le corresponde a cada dígito, de acuerdo con el lugar que ocupa dentro de la serie numérica. Como exponentes utilizaremos el “0”, “1”, “2”, "3" y así sucesivamente, hasta llegar al "7", completando así la cantidad total de exponentes que tenemos que utilizar con ese número binario. La descomposición en factores la comenzamos a hacer de izquierda a derecha empezando por el mayor exponente, como podrás ver a continuación en el siguiente ejemplo: 101111012 = (1 . 27) + (0 . 26) + (1 . 25) + (1 . 24) + (1 . 23) + (1 . 22) + (0 . 21) + (1 . 20) = (128) + (0) + (32) + (16) + (8) + (4) + (0) + (1) = 18910 En el resultado obtenido podemos ver que el número binario 101111012 se corresponde con el número entero 189 en el sistema numérico decimal. Conversión de un número entero del sistema numérico decimal al sistema de binario. Seguidamente realizaremos la operación inversa, es decir, convertir un número perteneciente al sistema numérico decimal (base 10) a un número binario (base 2). Utilizamos primero el mismo número 189 como dividendo y el 2, correspondiente a la base numérica binaria del número que queremos hallar, como divisor. A continuación el resultado o cociente obtenido de esa división (94 en este caso), lo dividimos de nuevo por 2 y así, continuaremos haciendo sucesivamente con cada cociente que obtengamos, hasta que ya sea imposible continuar dividiendo. Veamos el ejemplo:

Una vez terminada la operación, escribimos los números correspondientes a los residuos de cada división en orden inverso, o sea, haciéndolo de abajo hacia arriba. De esa forma obtendremos el número binario, cuyo valor equivale a 189, que en este caso será: 101111012

6 / 11

Cambio de bases. En un sistema posicional de base b se suelen utilizar b dígitos para representar los números. Comúnmente los dígitos empleados son 0, 1, …, |b|-1, y para dígitos mayores a 9, generalmente se emplean letras mayúsculas, por ejemplo A= 10, B= 11, etc. Según la base que escojamos, tendremos una representación conocida como sistema de numeración. Se les denomina sistemas posicionales ya que el primer dígito a la izquierda del punto decimal (las unidades) conserva su propio valor, mientras que cada que nos movemos un lugar a la izquierda, el valor del dígito se multiplica por b (esto es, cambia según su posición). Las bases más comúnmente utilizadas son la 10 (decimal) que es la que normalmente empleamos, la 2 (binaria) y la 16 (hexadecimal) que son ampliamente usadas en la computación. Al escribir un número entero, anotamos todos los dígitos de forma sucesiva n = akak-1…a0, aunque en realidad lo que estamos expresando es n = akbk + ak-1bk-1 + … + a0b0. Cabe señalar que b0 = 1. Por ejemplo, si tenemos el número 1982 en base 10, lo que estamos representando es 1×103 + 9×102 + 8×10 + 2. Cuando se utilizan varias bases al representar números, se acostumbra anotar como subíndice al final del número la base, por ejemplo: 2510 = 318 (25 base diez es igual a 31 base ocho). Si no se especifica la base, se sobreentiende que se trata de base diez. Algunas veces se utilizan prefijos para identificar bases, por ejemplo en Pascal se utiliza el signo de pesos (‘$’) y en C un cero y una x (‘0x’) para denotar los números hexadecimales. Para un número fraccionario, lo que hacemos es separar la parte fraccionaria de la entera mediante un punto y escribir la parte fraccionaria mediante potencias negativas de la base. Por ejemplo, = 7.5 = 7×100 + 5×10-1. Comúnmente se utilizan como base algún número natural, aunque también es posible recurrir a números negativos (como las bases negadecimal y negabinario), números irracionales (como π), e inclusive bases complejas (como 1+i). En bases no naturales se puede dar el caso de que un número tenga más de una representación. Para convertir de una base (b1) a otra (b2), podemos utilizar alguno de los siguientes algoritmos: Teniendo que n = akb1k + ak-1b1k-1 + … + a0b10, convertimos el valor de b1 y todas las ai (0 ≤ i ≤ k) a su equivalente en b2 y realizamos las operaciones de suma y multiplicación en esta base. Por ejemplo, si queremos pasar 217 de base 8 a base 5, tenemos que: 2178 = (2×82 + 1×81 + 7×80)8 = (2×132 + 1×131 + 12×130)5 = (2×132 + 13 + 12)5 = (1003 + 13 + 12)5 = 10335 El inconveniente obvio que presenta este método es que necesitamos tener la conversión de todos los dígitos de la base b1 a la base b2 para poder convertir el número completo. Por esto, este método es útil principalmente cuando b1 < b2. Otra forma para convertir entre bases es ir dividir el número en base b1 entre b2, tomar el cociente y repetir hasta que el cociente sea cero. Al final, el número en base b2 se conforma por los residuos, leyéndolos del último al primero. Utilizando los mismos números y bases del ejemplo anterior, tenemos que (las operaciones son en base 8):

2178 = 10335 Si queremos convertir entre bases, y una de estas es potencias de la otra, existe una forma para hacer más rápida la conversión. Teniendo que b2 = b1i, entonces podemos separar al número en base b1 en bloques de tamaño i, convertir esos bloques y después unirlos. Por ejemplo, si queremos cambiar 7BE de base 16 a base 2, sabemos que 716 = 01112, B16 = 10112 y E16 = 1110, por lo que 7BE16 = 0111101111102 (podemos omitir el primer cero). Si ahora lo queremos pasar a base 8, lo separamos en bloques de 3: 0111101111102 → 0112110211121102, como 0112 = 3, 1102 = 6 y 1112 = 7, entonces 0111101111102 = 36768. Para convertir un número con decimales a otra base, podemos utilizar el siguiente algoritmo. Para la parte entera, utilizamos cualquiera de los métodos anteriores y para la parte decimal realizamos lo siguiente: multiplicamos los decimales de b1 por b2, la parte entera del resultado la tomamos como el primer dígito de la conversión y con la parte decimal repetimos el procedimiento. Por ejemplo, para pasar 0.2205 de base 6 a base 2 (las operaciones son en base 6):

7 / 11

0.2205 × 2 = 0.4414 0.4414 × 2 = 1.3232 0.3232 × 2 = 1.0504 0.0504 × 2 = 0.1412 0.1412 × 2 = 0.5224 0.5224 × 2 = 1.2452 Por lo tanto, el resultado es 0.22056 = 0.011001…2 Nota: un número que tiene una cantidad finita de decimales en una base puede tener una cantidad infinita en otra Ejemplo La compañía Really Neato Calculator SA de CV ha contratado recientemente a tu equipo para ayudarlos a diseñar la calculadora Super Neato Model I. Como científico en computación, sugieres a la compañía incluir en la calculadora una función para convertir entre bases numéricas. La compañía la considera una idea estupenda, y le ha pedido a tu equipo que se encargue del programa prototipo para la conversión de bases. El director encargado de la Super Neato Model I te ha informado que la calculadora cuenta con las siguientes características:  Tendrá una pantalla de 7 dígitos.  En los botones se incluirán las letras mayúsculas A a F, además de los dígitos 0 a 9.  Tendrá soporte para las bases 2 a 16. Entrada La entrada para el programa prototipo consistirá en una conversión por línea. Habrá tres números por línea. El primero de ellos será el número en la base original, el segundo la base origen y el tercero la base a convertir. Habrá uno o varios espacios en blanco a cualquier lado de los números. Existen varias líneas en la entrada, y tu programa deberá continuar hasta llegar al fin de archivo. Salida En la salida sólo deberá estar el número convertido, tal y como aparecería en la pantalla de la calculadora. El número deberá estar justificado a la derecha 7 dígitos. Si el número es demasiado grande para aparecer en el display, debes imprimir “ERROR” (sin las comillas) justificado a la derecha. Solución: Para cambiar de una base a otra, vamos a utilizar como paso intermedio la base 10. Esto se debe a que si quisiéramos omitir la conversión intermedia, necesitaríamos tener implementaciones de las operaciones básicas (+, -, ×, ÷) en todas las bases. Casos ejemplo Entrada: 2102101 3 10 Desarrollo: 2102101 r= 0 t= 2, r= 3*0 + 2= 2 t= 1, r= 3*2 + 1= 7 t= 0, r= 3*7 + 0= 21 t= 2, r= 3*21 + 2= 65 t= 1, r= 3*65 + 1= 196 t= 0, r= 3*196 + 0= 588 t= 1, r= 3*588 + 1= 1765 r= '' t= 1765 mod 10= 5, r= '5' t= 176 mod 10= 6, r= '65' t= 17 mod 10= 7, r= '765' t= 1 mod 10= 1, r= '1765' length('1765')= 4 ≤ 7 1765 Salida:

Entrada: 12312 4 2 Desarrollo: 12312 r= 0 t= 1, r= 4*0 + 1 = 1 t= 2, r= 4*1 + 2 = 6 t= 3, r= 4*6 + 3 = 27 t= 1, r= 4*27 + 1 = 109 t= 2, r= 4*109 + 2 = 438 r= '' t= 438 mod 2= 0, r= '0' t= 219 mod 2= 1, r= '10' t= 109 mod 2= 1, r= '110' t= 54 mod 2= 0, r= '0110' t= 27 mod 2= 1, r= '10110' t= 13 mod 2= 1, r= '110110' t= 6 mod 2= 0, r= '0110110' t= 3 mod 2= 1, r= '10110110' t= 1 mod 2= 1, r= '110110110' length('10010110110')= 9 > 7 ERROR Salida: 8 / 11

En las primeras tres líneas declaramos las variables que vamos a utilizar: s es la cadena en la que guardamos el número original, i es para los ciclos, b1 y b2 son la base original y la base a convertir, respectivamente. El tamaño de s es de 7 para leer únicamente los primeros 7 caracteres. En la siguiente función (líneas 5 a 16) cambiamos de la base original a base 10. Como parámetros tenemos el número original n en forma de cadena y la base original b. La variable i la utilizamos para los ciclos, t como variable temporal y r para guardar el resultado. Empezamos inicializando el resultado a cero (línea 8), y revisamos dígito por dígito el número original (línea 9 a 14). Entre las líneas 11 y 12 pasamos el dígito de caracter a número: si el dígito está entre 0 y 9, entonces restamos 48 (ASCII del cero), en caso contrario, restamos 55 (ASCII de la A mayúscula menos diez). Después multiplicamos el resultado temporal por la base (equivale a incrementar en uno todas las potencias) y le agregamos el nuevo número. Terminamos regresando el resultado (línea 15). En seguida tenemos la función que cambia un número de base 10 a otra base (líneas 18 a 33). Utilizamos el mismo nombre de variables para el mismo uso, sólo que cambiamos algunas cadenas a enteros y viceversa. Empezamos inicializando el resultado (líneas 22 y 23), tomando en cuenta el caso especial en que n es cero. Para cambiar el número de base, utilizamos el método de dividir entre la nueva base hasta llegar a cero (líneas 24 a 30). Esto lo hacemos dividiendo el número entre la base y agregando cada residuo al final de r (teniendo en cuenta que el resultado es una cadena). Acabamos revisando si el resultado cabe en la pantalla (esta línea se debe omitir en otros programas) y regresándolo. 9 / 11

La parte principal del código la tenemos entre las líneas 35 a 42, en la cual repetimos el proceso mientras no lleguemos al fin de archivo. En la línea 38 leemos el número, la base en la que está y la base a la que lo cambiaremos. Después de leer el número, parchamos los espacios con ceros (líneas 39 y 40). Por último, escribimos el resultado del cambio de bases (línea 41).

Descomposición en factores primos Cualquier número entero positivo se puede representar de forma única (salvo el orden) como el producto de una serie de factores primos. Seguramente ésto nos lo tenemos bien aprendido desde los tiempos del colegio, pero computacionalmente la cosa no es tan sencilla. Este artículo ya lleva un tiempo escrito y publicado en éste sitio, pero hemos cambiado un poco el formato y hemos introducido una demo en línea del algoritmo propuesto. A ésta características de los números enteros positivos se le llama el teorema fundamental de la aritmética1. Esta propiedad tan sencilla a simple vista trae enormes quebraderos de cabeza desde el punto de vista de la computación. Este teorema tiene aplicaciones prácticas en muchos campos, aunque en los últimos años su mayor aplicación está en la criptografía. El motivo es muy sencillo, y vamos a intentar intuirlo en este artículo. En el cole aprendimos un algoritmo simple para obtener la factorización de un número entero en sus factores primos. Haciendo un breve repaso, éste algoritmo consiste simplemente en coger un número natural n, y probar a dividirlo por los números primos, empezando por el 2, luego el 3, luego el 5... cuando el resto de la división es 0, hemos obtenido un factor, hacemos que n valga ahora el cociente, y seguimos probando por el último primo en el que estábamos. Así indefinidamente hasta que n=1 Examinando cómo lo hacemos a mano... Por ejemplo, para factorizar el 350, hacemos n=350... y empezamos a probar a dividir por los números primos. Probamos a dividir n por 2... 350/2=175, y resto 0... perfecto, hemos encontrado un factor: el 2. Hacemos n=175 Lo volvemos a intentar 175/2 = 87 y resto 1... oops... el 2 no vuelve a ser factor primo. Pasamos a probar con el 3. 175/3=58 y resto 1... el 3 no es factor primo. Pasamos al 5. 175/5=35 y resto 0 ... el 5 es factor primo. Tomamos nota (ya tenemos el 2 y el 5), y hacemos n=35 Volvemos a probar el 5... 35/5=7 y resto 0. Otra vez el 5 es factor primo (ya tenemos 2, 5 y 5). Hacemos n=7 Volvemos a probar el 5... 7/5=1 y resto 2. Ya no hay más cincos. Probamos con el 7. 7/7=1 y resto 0. El siete es factor primo (ya tenemos 2, 5, 5, y 7). Hacemos n=1... ya hemos terminado. Así pues, 350 se puede expresar como 350=2 x 5 x 5 x 7. El procedimiento es sencillo... pero... ¿Seremos capaces de encontrar un buen algoritmo que dado un número natural n nos devuelva sus factores primos? Encontrar un algoritmo Para encontrar un algoritmo de factorización nos encontramos con una serie de problemas. El primero de ellos es que si te das cuenta, vamos avanzando por la lista de números primos... 2, 3, 5, 7... pero ¿Cómo se construye esta lista? La primera persona de quién se tiene constancia de que se planteó este problema parece ser el matemático Eratóstenes, que nos dejó el algoritmo conocido como Criba de Eratóstenes?. Este algoritmo permite hallar los números primos menores que un número natural dado, pero el algoritmo es computacionalmente complejo.... tanto como el de la propia factorización. Además... el algorimo exige un gran gasto de memoria, ya que si estamos descomponiendo el 350, necesitaremos una lista que ocupará unos pocos bytes, pero si estamos descomponiendo un número de 16 o 20 cifras, necesitaremos una cantidad de memoria que probablemente no nos podamos permitir. Existe una forma de no construir la criba de Eratóstenes. Si nos damos cuenta, sólo hay un factor primo par: el 2. Todos los demás son impares. Podemos hacer que nuestro algoritmo intente dividir por el 2, y luego por todos los impares, aunque no sean primos. El algoritmo seguirá funcionando, porque cuando intente dividir por un número compuesto, por ejemplo, el 35 (7*5), se descartará siempre porque el resto no será 0, ya que el algoritmo ya habrá dividido previamente por sus factores (el 5 y el 7). Esto, que parece un desperdicio, es más eficiente que construir una criba de Eratóstenes. 1

En matemática, y particularmente en la teoría de números, el teorema fundamental de la Aritmética o teorema de factorización única afirma que todo enteropositivo se puede representar de forma única como producto de factores primos. El teorema establece la importancia de los números primos. Éstos son los «ladrillos básicos» con los que se «construyen» los enteros positivos, en el sentido de que todo entero positivo puede construirse como producto de números primos de una única manera. 10 / 11

Supongo que en este momento te estarás preguntando si existe alguna forma sencilla de saber si un entero es primo o no. La respuesta es que si esa prueba existe, nadie la ha descubierto todavía. (Si encuentras esa prueba sencilla y demuestras que funciona te harás inmensamente rico... mucha gente lo está intentando en este momento, pero no parece que haya avances revolucionarios). En el contexto de nuestro problema, mejor olvidarnos de la prueba... ninguna va a ser tan sencilla como probar a dividir a ver si el resto es 0, aunque el divisor sea compuesto. Por otro lado... ¿Hasta dónde tenemos que llegar en la lista de divisores?. Quiero decir... si estamos intentando descomponer el 4731, sabemos que paramos cuando n=1, pero ¿Y si no llegamos a esa condición? ¿Cuándo paramos? Parece bastante obvio que el peor caso que nos podemos encontrar es que el 4731 sea primo, con lo cual, pararíamos al dividir 4731/4731=1 y resto 0. Haríamos n=1 y ya tenemos la condición de terminación... pero ¿Podemos parar antes? Afortunadamente sí. Un matemático marroquí del siglo XIII llamado Al-Marrakushi Ibn al-Banna demostró que basta con probar con los numeros inferiores o iguales a la raíz cuadrada de n. Si llegados a ese punto, n es mayor que 1, entonces n contiene el último de los factores primos. Vale, con este par de optimizaciones ya podemos construir un algoritmo de factorización. Iremos probando a dividir un número dado n por 2, y luego por todos los impares, hasta llegar a la raíz cuadrada de n. Cada vez que obtengamos un resto 0, hemos encontrado un factor primo, y asignaremos a n el cociente de la división para seguir probando. El caso es que no se han encontrado algoritmos lo suficientemente buenos como para considerarse "revolucionarios" dentro de este tema. No obstante, nos vamos a quedar con estas dos optimizaciones, que son las que comunmente sirven para construir un algoritmo de factorización sencillito. Aquí tienes un posible algoritmo que refleja lo que hemos comentado escrito en pseudocódigo 1 Variables: n,num1:entero; 2 cuenta:entero; 3 n=numero a factorizar; 4 num1:=n; //no queremos perder n 5 6 //Primero comprobamos si 2 es un factor de num1 7 mientras num1 mod 2=0 hacer 8 escribir(2); 9 num1:=num1/2; //division entera 10 finMientras 11 12 //Ahora probamos con el resto de los impares 13 cuenta:=3; 14 //Solo hasta llegar a la raiz cuadrada de num 15 16 mientras (cuenta<=raiz(num)) y (num1>1) hacer 17 Si num1 mod cuenta=0 entonces 18 escribir(cuenta); 19 num1:=num1/cuenta; 20 end 21 si no 22 cuenta:=cuenta+2 23 finSi 24 finMientras 25 26 //Si hemos acabado porque num1=1 entonces nada, 27 //pero si hemos acabado porque hemos alcanzado la 28 //raiz de n, entonces, num1 contiene el último factor 29 Si num1>1 entonces 30 escribir(num1); 31 finSi

11 / 11