comando de factor imprime los factores primos de número entero especificado NÚMERO.¿Cuál es el algoritmo detrás del comando de factor en Linux?
cuando lo probé
factor 12345678912345678912
incluso para un número tan grande, que los resultados dentro de los molinos.
que algoritmo usa?
El manual de Gnu coreutils informa que Pollard's rho algorithm se está utilizando.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
He aquí un ejemplo de una versión de la fuente de factor de GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Incluye rutinas tanto de la división de ensayo y rho de Pollard. Me parece en un análisis rápido como si usa división de prueba para encontrar algunos pequeños factores (hasta aproximadamente lg(n)^2, que es aproximadamente 4000 en este caso), y luego Pollard si lo que queda no es probablemente el primero. En este caso, eso es 205432623008947 si estoy en lo cierto sobre el 4000, es decir, 35129 * 5847949643.
El segundo mayor factor primordial en su ejemplo es 35129, y la raíz cuadrada de la más grande es alrededor de 76471. Así que la división de prueba por sí sola sería rápida, ya que solo tiene que probar unos 25 mil candidatos.