Cómo aprovechar al máximo el día de trampa

Question

Por ejemplo, tengo el número $420$. Este puede dividirse en su facturización primera de %#% $ #%

Utilizando $$2^2 \times3^1\times5^1\times7^1 = 420 $$$\prod_{i=1}^r (a_r + 1)$ $ where $r $ is the magnitude of the power a prime factor is raised by and $ 24$ posibles factores.

¿Hay una manera fácil de recorrer en iteración todos los factores de #% de %#% para obtener todas las $ is the number of prime factors. I get $? Sé que esto puede hacerse fácilmente con una tabla de números con sólo factores de $4$. Pero, como éste tiene $24$ obviamente no puedo llevar a la práctica el método de la tabla. ¿Así que cualquier solución para ello? ¡Gracias!

Answer 1

Expanda la siguiente expresión: $$(2^0+2^1+2^2)(3^0+3^1)(5^0+5^1)(7^0+7^1)$$ Cada combinación de las cuatro opciones (por ejemplo,$2^2, 3^1, 5^0, 7^1$, cuyo producto es $2^23^15^07^1=84$) da un claro factor de $420$.

Answer 2

A modo de ejemplo de una tabla de factores, sólo para comprobar que estamos hablando de lo mismo:

Los factores de $8=2^3$ son de curso acaba de $2^0, 2^1, 2^2, 2^3$ o calculada $1,2,4,8$.

Los factores de $9=3^2$ $3^0, 3^1, 3^2$ aka $1,3,9$.

Ahora los factores de $72$ puede ser formado por la combinación de dos números elegidos, uno por cada uno de estos dos juegos:

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 8 \\\hline 1 & 1 & 2 & 4 & 8 \\ 3 & 3 & 6 & 12 & 24 \\ 9 & 9 & 18 & 36 & 72 \\ \end{array}

Este es sin duda el tipo de tabla que usted está pensando.

Para $420$ podríamos aplicar este proceso varias veces, alimentar el contenido de cada tabla en uno de los ejes de la siguiente tabla:

\begin{array}{c|ccc} \times & 1 & 2 & 4 \\\hline 1 & 1 & 2 & 4 \\ 3 & 3 & 6 & 12 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60 \\ \end{array}

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

o por un poco más atractivo de la mesa final podríamos dividir los factores que en mayor igualdad de subconjuntos, aquí los factores de $2^23^1 =12$ a través de la parte superior y los factores de $5^17^1=35$ al lado.

\begin{array}{c|ccc} \times & 1 & 2 & 4 & 3 & 6 & 12 \\\hline 1 & 1 & 2 & 4 & 3 & 6 & 12 \\ 5 & 5 & 10 & 20 & 15 & 30 & 60\\ 7 & 7 & 14 & 28 & 21 & 42 & 84 \\ 35 & 35 & 70 & 140 & 105 & 210 & 420\\ \end{array}

Answer 3

Así que... sí. Son todos los números que están en la forma $2^a3^b5^c7^d$ donde $0 \le a \le 2; 0 \le b\le 1; 0 \le c\le 1;0 \le d\le 1;$

Sólo la lista de todos ellos:

$2^03^05^07^0 = 1$

$2^13^05^07^0 = 2$

$2^23^05^07^0 = 4$

$2^03^15^07^0 =3$

$2^13^15^07^0 =6$

....etc...

Escribir menos: son $1,2,4,3,6,12,5,10,20,15,30,60,7,14,28,21,42,84,35,70,140,105,210,420$

En general si $N=\prod p_i^{k_i}$ sólo la lista de todos los posibles $\prod p_i^{m_i}$ donde para cada $m_i$ $0\le m_i \le k_i$.

Answer 4

Si $n = \prod_{i=1}^r p_i^{a_i} $ es la factorización prima en $n$, hay $\prod_{i=1}^r (a_i + 1) $ los factores primos.

Mira este como contar una $r$-número de dígitos en una variable de base, con la base de la $i$-ésimo dígito $a_i+1$, de manera que ese dígito va de $0$ $a_i$. Si $b_i$ $i$- ésimo dígito, a continuación, el valor correspondiente a ese dígito es $p_i^{b_i}$.

Aquí es mi opinión en un moderado algoritmo eficiente para calcular todos los los factores posibles. El divisor se inicia en $1$. Cuando un dígito se incrementa, el valor del divisor se multiplica por $p_i$. Si el $i$-ésimo dígito supera $a_i$, se pone a cero, el divisor divide por $p_i^{a_i}$, y el siguiente dígito es examinado.

Inicializar $d = 1$ (el divisor) y $b_i = 0$ y $c_i = p_i^{a_i}$ para $i=1$ $r$(los exponentes y max poderes de $p_i$).

$\text{hacer para siempre}\\ \quad\text{salida } d\\ \quad\text{para }i=1\text{ a }r\\ \qquad \text{si } b_i<a_i\text{ entonces } b_i=b_i+1; d=d\cdot p_i; \text{ salida para el bucle} \quad\text{(dígito no desbordamiento)}\\ \qquad\text{else } b_i=0; d=d/c_i \quad\text{(dígito desbordó - reset y buscar en el siguiente dígito)}\\ \quad\text{end}\\ \quad\text{si }d=1\text {, a continuación, salir del bucle} \quad\text{(todos los dígitos se desbordó hecho)}\\ \text{end do}\\ $