Si n = a * b * c, ¿cuál es el algoritmo más rápido para obtener todos los valores enteros posibles para a, byc provistos de prueba si es posible?

Answer 1

Otros se han ocupado de los problemas derivados de la factorización. Supongamos que hemos logrado encontrar de manera eficiente una factorización en términos de potencias principales

[matemáticas] n = p_1 ^ {k_1} p_2 ^ {k_2} \ cdots p_m ^ {k_m} [/ matemáticas]

Por ejemplo [matemáticas] 360 = 2 ^ 3 3 ^ 2 5 ^ 1 [/ matemáticas]. La última parte de la respuesta es enumerar todos los triples posibles.

[matemáticas] a = p_1 ^ {\ alpha_1} p_2 ^ {\ alpha_2} \ cdots p_m ^ {\ alpha_m} [/ math]

[matemáticas] b = p_1 ^ {\ beta_1} p_2 ^ {\ beta_2} \ cdots p_m ^ {\ beta_m} [/ matemáticas]

[matemáticas] c = p_1 ^ {\ gamma_1} p_2 ^ {\ gamma_2} \ cdots p_m ^ {\ gamma_m} [/ matemáticas]

Con [math] \ alpha_1 + \ beta_1 + \ gamma_1 = k_1 [/ math] etc. Para cada primo solo puede usar un doble bucle

for i = 0 to k1 then

for j = 0 to k1 - i then

alpha1 = i

beta1 = j

gamma1 = k1 - i - j

Es necesario tener cuidado para eliminar los casos en que uno de a, b o c es 1. Probablemente sea más sencillo encontrar todas las soluciones y simplemente eliminar las degeneradas.

Answer 2

Como dijo Marcas Neal, el factoring parece ser un problema difícil. De Wikipedia Factorización entera:

Se sospecha que está fuera de las tres clases de complejidad P, NP-complete y co-NP-complete. Por lo tanto, es un candidato para la clase de complejidad NP-intermedia.

Sin embargo, si tenemos algunos límites en el problema, podríamos ser capaces de hacer un algoritmo eficiente. Supongamos que sabemos que [matemáticas] n

1. Por ejemplo, si sabemos que [matemáticas] N [/ matemáticas] es pequeño, y queremos buscar / consultar la respuesta para muchas [matemáticas] n [/ matemáticas] s, podríamos hacer una tabla de las respuestas por cada [matemática] n [/ matemática].

2. Si [math] N [/ math] es un poco más grande y estamos haciendo menos consultas, es posible que queramos calcular las factorizaciones sobre la marcha (en línea), pero mantenga una tabla de primos conocidos hasta [math] \ sqrt {N} [/ math].

3. Si [math] N [/ math] es muy grande y estamos haciendo pocas consultas, es posible que no podamos almacenar los primos conocidos hasta [math] \ sqrt {N} [/ math]. Luego tenemos que usar los algoritmos ineficientes mencionados en el artículo de Wikipedia.

¿Cuándo es 2 mejor que 1? Cuando se espera que el número de consultas sea menor que [math] N [/ math].

Para 1, podemos factorizar todos los números haciendo una tabla de números primos y potencias primarias hasta [math] \ sqrt {N} [/ math], y observando cada número que es un múltiplo de cada uno. Cualquier factor restante es primo.

Para 2, podemos factorizar un número comparándolo con cada primo en nuestra tabla usando el operador de módulo.

Las tablas Prime se pueden construir usando el Tamiz de Eratóstenes, aunque puede haber mejores formas.

Supongamos que nuestro número está factorizado. Es decir, sabemos [matemáticas] n = p_1 ^ {e_1} \ cdot p_2 ^ {e_2} \ cdot… \ cdot p_k ^ {e_k} [/ math], donde [matemáticas] p_1

Ahora suponga que solo tiene que elegir una [matemática] aleatoria a, b, c [/ matemática]. No tienes que calcular todas las posibilidades. Para [matemática] a [/ matemática], elija el poder de [matemática] p_i [/ ​​matemática] para que sea 0 con probabilidad [matemática] \ frac {e_i + 1} {\ frac {(e_i + 1) (e_i +2 )} {2}} [/ math], ser 1 con probabilidad [math] \ frac {e_i} {\ frac {(e_i + 1) (e_i +2)} {2}} [/ math] y así sucesivamente , luego elija el exponente en [matemática] p_i [/ ​​matemática] para [matemática] b [/ matemática] uniformemente entre 0 y [matemática] e_i [/ ​​matemática] menos la potencia en [matemática] a [/ matemática]. Repita para cada [math] p_i [/ ​​math].

Answer 3

Si encuentra un algoritmo que lo hace en tiempo P, * NO * ¡compártelo con la NSA! 😉

No existe un algoritmo “rápido” para completar la tarea anterior. Si lo resuelve, ha resuelto uno de los santos griales de la informática.