¿Cómo encontrar todos los factores primos de un entero sin signo de largo tiempo?

Question

Tengo una tarea de encontrar todos los factores primos de un número ...

Tengo que escribir una función que toma un número y me dice todo los factores primos del número. Por ejemplo:

• n = 350 factores primos: 2 5 5 7

(I pasar a la función de un número en el rango de 0 a 18446744073709551615 - el número máximo es el mayor número que cabe en un 64 bits sin signo largo entero largo.)

Answer 1

Esto es un problema difícil, y una de las principales razones de toda la investigación en los ordenadores cuánticos. Echar un vistazo a algoritmo de Shor . Simple fuerza bruta sin optimizaciones tomaría algo así como 1000 años, aunque en este caso específico (enteros de 64 bits), debe ser capaz de reducir su tiempo de ejecución a tan sólo unos minutos.

Asumiendo que tiene un caso trivial de (como máximo) uno de los factores primos grandes, se puede acelerar significativamente haciendo algo como contar desde 2 y tratando cada número (varias veces si funciona; 12 sería de 2, 2, y 3 por ejemplo). Después de encontrar un factor, reducir el número de destino por ese factor y probar si el nuevo objetivo es primo.

Para acelerarlo aún más, se podría hacer a través de múltiples hilos de procesamiento, con cada uno a cargo de una serie de divisores. Usted podría funcionar probadores de primalidad en uno o más hilos, proporcionando números primos al hilo de pruebas por lo que sólo está tratando de dividir por números primos.

Incluso podría buscar desde la parte superior de la gama abajo, si cree que la persona que proporciona el valor está tratando de ser tricksome, aunque con la densidad de los números primos es mucho más alto en el extremo inferior, esto probablemente no ayudará .

Lo principal a recordar, sin embargo, que el mayor factor posible de X, además de por sí X, es la raíz cuadrada de X. Cada vez que encuentre un factor, el mayor factor restante posible disminuye significativamente.