Descomposición en números primos

Question

¿Cuál es la forma más rápida de descomponer el número dado en números primos sin usar calculadora?

Ejemplo: $$3575$$

Lo que hago es:

$$3575 = 3 \times 10^3 + 5 \times 10^2 + 7 \times 10 + 5 = 3\times5^3\times2^3 + 5^2 \times 2^2 \times 5 + 7 \times 5 \times 2 + 5$$

Pero ahora no sé cómo deshacerme efectivamente del "$+$".

Answer 1

Por inspección, los dos últimos dígitos de $75$ significa que $3575$ es divisible por $25=5^2$. Luego, el resultado de dividir por $25$ es $\frac{3500}{25} + \frac{75}{25}=4\times 35+3 = 143=12^2-1 = 11\cdot 13$, lo que da $3575 = 5^2\cdot11\cdot13$

Answer 2

La forma más rápida en general es mediante algún algoritmo "rápido", ya sea mediante computadora o a mano. No hay atajos en general. Existen muchos algoritmos de factorización de enteros, pero el tiempo de ejecución es, incluso para el tamiz general de teoría de números, dado por $${\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)} $$ para un número de $b$ bits $n. Para $n=3575$ obtenemos $5^2\cdot 11\cdot 13$. Aquí podríamos intentar primero con pequeños divisores primos.

Answer 3

$$ 3600 - 25 = 60^2 - 5^2 = (60 + 5) (60 - 5) = 65 \cdot 55 $$ Entonces vemos que $65 = 5 \cdot 13$ y $55 = 5 \cdot 11$

Esto suele llamarse factorización de Fermat. Comienza con el primer cuadrado mayor que el número, ve si la diferencia es un cuadrado. Si eso no funciona, toma el siguiente cuadrado justo mayor que ese. Para ahorrar tiempo, podemos descartar algunos cuadrados ya que la diferencia no puede ser $3 \pmod 4$ o $2 \pmod 4.$ En este caso, $61^2 - 3575 = 146 \equiv 2 \pmod 4 $ no puede ser un cuadrado. Saltaríamos a $62^2 - 3575,$ luego $64^2 - 3575.$ Sin embargo, la primera vez funcionó.

Si te diera $9991$ el siguiente cuadrado mayor sería $10000$ y $10000 - 9991 = 9,$ entonces $9991 = (100 +3)(100-3) = 103 \cdot 97$