programacion ejercicio

ADDA
 

1a
 Práctica
 individual
 
 

Curso
 2014/2015
 


 
Problema 6
Enunciado y preguntas:
 
En teoría de números, la factorización de enteros ofactorización de primos consiste en
descomponer un número compuesto (no primo) en divisores no triviales, que cuando se
multiplican dan el número original.
Por el teoremafundamental de la aritmética, cada entero positivo tiene una única
descomposición en números primos (factores primos). La mayor parte de los algoritmos
de factorización elementales son depropósito general, es decir, permiten descomponer
cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de
ejecución.
Para nuestro propósito académico, queremosconocer cuál es la cantidad de veces que
un factor determinado está contenido en un número factores de un número.
Por ejemplo, el 2 está contenido en el 40 tres veces, ya que 40 = 23x 5 y está contenido
en el 50 una única vez, ya que 50 = 2 x 52. Sin embargo, no está contenido en el 81, ya
que 81 = 34.
Preguntas
1. Defina la función recursiva no final quepermita determinar la cantidad de veces
que un número está contenido en otro como factor (explicación del enunciado).
2. Calcule el T(n) y la complejidad del algoritmo.
3. Implemente unafunción recursiva no final empleado el lenguaje de
programación que le ha indicado su profesor que solucione el problema
planteado, partiendo del siguiente prototipo (el prototipoestá en lenguaje natural
para que lo aplique al lenguaje que le ha sido asignado como corresponda:
!"#!$%  !"#$%&'(!(  !"#!$%  !"#$%&'!"#$%&'", !"#!$%  !"#$%&  )
4. Implemente unafunción recursiva final a partir de la definición anterior.
5. A partir de las funciones anteriores, diseñar e implementar un algoritmo
iterativo que solucione el problema planteado.