Factorizacion en C#

FACTORIZACIÓN C#
INTRODUCCIÓN
En teoría de números, la factorización de enteros o factorización de primos consiste en
descomponer un número compuesto (no primo) en divisores no triviales, quecuando se
multiplican dan el número original.

Por el teorema fundamental de la aritmética, cada entero positivo tiene una única
descomposición en números primos (factores primos). La mayor parte delos algoritmos
de factorización elementales son de propósito general, es decir, permiten descomponer
cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de
ejecución.Por tanto lo que pretendemos es conocer el número de divisores (repetidos o no) de
un número entero cualquiera.

GLOSARIO DE TÉRMINOS





Tamaño: entero mayor o igual que cero que nos dauna idea de la complejidad del problema.



Caso Base: problema de tamaño pequeño cuya solución es directa, no recursiva.



Caso Recursivo: resto de problemas.

FACTORIZACIÓN C#Javier Guisado Torres IS G3

APARTADO A)
Dé una definición recursiva para obtener el número de divisores de un número
entero:

La definición recursiva dada es recursiva final:
𝐹𝑜𝑟𝑚𝑎 𝐹𝑖𝑛𝑎𝑙(𝑎, 𝑛) {𝑎
𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑧𝑎𝑐𝑖𝑜𝑛𝐹𝑖𝑛𝑎𝑙(𝑛/𝑎, 𝑐𝑜𝑛𝑡)

𝑠𝑖 𝑛 = 1
𝑠𝑖 𝑛 ≠ 1

Por tanto el código de la función recursiva final sería:
int factorizacionFinal(int n, int cont){
int r,i,n1;
if(n==1){
r=cont+1;}else{
cont++;
i=factores(n);
n1=n/i;
n=n1;
r=factorizacionFinal(n,cont);
}
return r;
}

FACTORIZACIÓN C#

Javier Guisado Torres IS G3

APARTADO B)

Indique la complejidad:
𝐾1
𝑇(𝑛) { 𝐾2+ 𝑇 ( 𝑛)
𝑎

𝑛=1
𝑛>1

𝑛
𝐾1 𝑒𝑠 𝑒𝑙 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑒𝑗𝑒𝑐𝑢𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑐𝑎𝑠𝑜 𝑏𝑎𝑠𝑒 𝑦 𝐾2 + 𝑇 ( ) 𝑒𝑠 𝑒𝑙 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑒𝑗𝑒𝑐𝑢𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑟𝑒𝑠𝑡𝑜.
𝑎
Vemos que la llamada recursiva tiene la forma de Ecuación en Recurrencia,así que aplicamos los pasos:
𝑛
𝑛
𝑇(𝑛) = 𝐾2 + 𝑇 ( ) → 𝑇(𝑛) − 𝑇 ( ) = 𝐾2
𝑎
𝑎
𝑎0 = 1

𝑎1 = −1

𝑏1 = 1

𝑑1 = 0

La K2 es una constante, por lo que se trata de un polinomio de grado 0 (𝑑1...