Cómo hacer un árbol de factores de un número entero (por ejemplo, 12 o 180)

Answer 1

Para ser más general: un árbol de factores para un número entero [matemáticas] N [/ matemáticas] es un árbol que descompone este número entero en sus factores, hasta los factores primos en las hojas. Entonces, si tomas los enteros de todas las hojas, obtienes la factorización prima para [math] N [/ math].

Aquí hay un procedimiento recursivo simple que puede usar para construir un árbol de factores binarios para cualquier número entero [math] N [/ math]:

# Codificamos nuestro árbol binario como un triple:
# (raíz, subárbol izquierdo, subárbol derecho).
factor_tree (N)
si (N es primo)
return (N, , )
más
F = factor primo más pequeño de N
return (N, factor_tree (N / F), factor_tree (F))

Tenga en cuenta que el árbol de factores binarios generalmente no es único, dado un número entero [math] N [/ math]. El árbol producido por el algoritmo anterior estará bastante desequilibrado (ya que agregamos una hoja en cada paso), pero sigue siendo un árbol de factores.

Aquí hay una implementación Python muy simple (pero no la más eficiente) de este algoritmo:

def factor_tree (n):
para i en xrange (2, n):
si n% i == 0:
return (n, factor_tree (n / i), factor_tree (i))
retorno (n, Ninguno, Ninguno)

Llamar a factor_tree (180) da como resultado:

(180, (90, (45, (15, (5, Ninguno, Ninguno), (3, Ninguno, Ninguno)),
(3, Ninguno, Ninguno)), (2, Ninguno, Ninguno)), (2, Ninguno, Ninguno))

que se puede visualizar como:

Mirando las hojas, puedes ver que

[matemáticas] 180 = 5 \ cdot 3 \ cdot 3 \ cdot 2 \ cdot 2 [/ matemáticas]

Answer 2

Para hacer un árbol de factores para un número, escriba ese número en la parte superior

Ahora haga las ramas para este número: números cuyo producto (multiplicación) le dará el número original

Aquí, 12 = 3 x 4 (puede tomar 6 y 2)

Ahora tiene la segunda capa de ramas: divida estas ramas nuevamente

Aquí, 4 = 2 x 2, 3 no se puede escribir como producto de dos números (los números deben ser mayores que 1)

Por lo tanto, su resultado final para Factores de 12 es 3, 2, 2 (debe contar solo esos números en las últimas ramas)

Si está tomando 12 = 6 x 2, entonces

El resultado final sería el mismo – 12: 2,2,3