Suponga que [math] n [/ math], [math] a [/ math], [math] b [/ math] son ​​enteros positivos donde [math] n [/ math] no es un número primo, como [math] n = ab [/ math] con [math] a \ geq b [/ math] y [math] (a – b) [/ math] es lo más pequeño posible. ¿Cuál sería el mejor algoritmo para encontrar los valores de [matemática] a [/ matemática] y [matemática] b [/ matemática] si se da [matemática] n [/ matemática]?

Answer 1

Aquí hay otro algoritmo que es realmente rápido.
Lo mostraré con un ejemplo.

Digamos que a = 17 yb = 7.
Entonces n = 119.

No sabemos a ni b, y comenzamos por encontrar el siguiente cuadrado por encima de 119.
Obviamente, esto es 121 u 11 ^ 2.
Ahora 121-119 = 2 y 2 no es un cuadrado.

Entonces buscamos el siguiente cuadrado arriba de 121.
Por supuesto, el siguiente cuadrado después de [matemáticas] 11 ^ 2 [/ matemáticas] es [matemáticas] 12 ^ 2 = 144 [/ matemáticas].
[matemáticas] 144 – 119 = 25 = 5 ^ 2 [/ matemáticas].

Ya casi hemos terminado porque ahora podemos escribir 119 como una diferencia de dos cuadrados: [matemáticas] 119 = 144 – 25 = 12 ^ 2 – 5 ^ 2 [/ matemáticas]

Recuerde que [matemáticas] a ^ 2 – b ^ 2 = (a + b) (ab). [/ Matemáticas]
Entonces [matemáticas] 12 ^ 2 – 5 ^ 2 = (12 + 5) (12-5) = 17 X 7 [/ matemáticas]

Así a = 17, b = 7.

Este algoritmo podría tomar muchas rondas si a >> b.
Por ejemplo, en n = 7 X 151 necesitas 47 intentos.
Sin embargo; Como se afirma que (ab) es pequeño, este no debería ser el caso.

Si conoce sus cuadrados de memoria, este algoritmo se guía maravillosamente para el cálculo mental. En realidad, Willem Bouman me dijo que así es como él factoriza los números.
Por cierto, él es probablemente la mejor calculadora mental holandesa viva.

Answer 2

Básicamente, queremos encontrar los factores de n, verificar la diferencia de los factores y optimizarla.
Prueba esto :

a = 1
b = n
diff = n-1 # Mayor diferencia posible
para un si n% a == 0:
b = n / a
si diff> = ba:
diff = ba
más:
imprimir a, b
rotura
a ++

Supongo que esto debería resolver; Complejidad del tiempo: ‘n’