Come trovare tutti i fattori primi di un intero long unsigned long?

Question

Ho un incarico per trovare tutti i fattori primi di un numero ...

Ho bisogno di scrivere una funzione che prende un numero e mi dice tutto i fattori primi del numero. Ad esempio:

• n = 350 fattori primi: 2 5 5 7

(passo alla funzione un numero compreso tra 0 e 18446744073709551615 - il numero massimo è grande numero che si inserisce in un 64 bit senza segno lungo intero lungo.)

Answer 1

Questo è un problema difficile, e uno dei motivi principali per tutte le ricerche nel computer quantistici. Date un'occhiata a di Shor algoritmo . Semplice forza bruta senza ottimizzazioni sarebbe voluto qualcosa come 1000 anni, anche se in questo caso specifico (interi a 64 bit), si dovrebbe essere in grado di ridurre il tempo di esecuzione a pochi minuti.

Supponendo di avere un caso banale di (al massimo) un grande fattore primo, è possibile accelerare notevolmente facendo qualcosa di simile a contare su da 2 e cercando ogni numero (più volte se funziona; 12 sarebbe 2, 2, e 3, per esempio). Dopo aver trovato un fattore, ridurre il numero di destinazione da quel fattore e verificare se il nuovo obiettivo è primo.

Per accelerarlo ulteriormente, si potrebbe fare di elaborazione tra più thread, con ogni responsabile di una serie di divisori. È possibile eseguire i tester di primalità su uno o più thread, fornendo numeri primi al thread test in modo che sta solo cercando di dividere per numeri primi.

Si potrebbe anche cercare dal top di gamma verso il basso, se si pensa la persona che fornisce il valore sta cercando di essere tricksome, anche se con la densità dei numeri primi essere così molto più alto alla fine bassa, questo probabilmente non aiuterà .

La cosa più importante da ricordare, però, che il più grande possibile fattore di X, oltre che per X stesso, è la radice quadrata di X. Ogni volta che si trova un fattore, il più grande fattore restante possibile diminuisce significativamente.