Was ist der schnellste Algorithmus, um alle Faktoren einer ganzen Zahl zu berechnen? [duplicate]

Ich habe diesen Codeblock geschrieben, aber die Berechnung nimmt viel Zeit in Anspruch … Können Sie mir helfen, einen effizienten Weg zu finden, dies zu tun?

int tag;
int* factors(int n)
{
    int a[1000000];
    for(int i=1;i<=n/2;i++)
        if(n%i==0)
            a[++tag]=i;
    a[++tag]=n;
    return(a);
}

Diese Brute-Force-Methode ist sehr komplex in Bezug auf die Komplexität … Gibt es eine bessere praktikable Lösung für dieses Problem?

Bis jetzt ist niemand auf eine gekommen viel schneller Algorithmus. Das muss nicht unbedingt heißen, dass es keine gibt, andererseits ist auch nicht bewiesen, dass es nicht viel schneller geht.

Eine Optimierung, die Sie vielleicht berücksichtigen möchten, ist, dass es nicht notwendig ist, bis zu n/2 zu suchen, Sie können bereits aufhören, wenn sqrt (n) erreicht ist.

… und achten Sie darauf, einen anderen Speicherort für Ihre Nummern zu wählen, wenn Sie wirklich eine Liste aller gefundenen Kandidaten zurückgeben möchten, wie bereits in “chris” -Kommentar erwähnt.

BEARBEITEN:

Da ich darauf hingewiesen wurde, dass es eine ziemlich große Auswahl an verfügbaren Algorithmen gibt, die in Bezug auf die Zeitkomplexität möglicherweise etwas schneller laufen als der, nach dem Sie gefragt haben, ist es möglicherweise angezeigt, ein paar Worte mehr als den oben angegebenen kurzen Kommentar hinzuzufügen.

Während neben der naheliegendsten Möglichkeit, etwas Rechenzeit zu sparen, indem man die Schleife einfach in 2er-Schritten durchläuft, nachdem man sie zuerst durch eine ungerade Zahl geteilt hat, noch einige andere Tricks zur Verfügung stehen, habe ich sie nicht erwähnt im Wesentlichen schneller in der oben gegebenen Antwort.

Der Hauptgrund, der zu dieser Entscheidung geführt hat, ist, dass zum Beispiel die Verringerung der Anzahl der Iterationen um den Faktor 2 wie ein großer Gewinn erscheint, verglichen mit dem erwarteten Wachstum der Laufzeit mit wachsenden Zahlen einen Gewinn, gemessen in a Konstante wird so klein, dass in der Komplexitätstheorie überhaupt kein Unterschied mehr gemacht wird und beide Algorithmen (fast) die gleiche Zeitkomplexität haben.

Auch wenn es möglich wäre, eine zu bekommen Konstante Durch den hundertmilliardenfachen Laufzeitgewinn des ursprünglichen Algorithmus würde zwischen beiden immer noch kein Unterschied gemacht werden.

Je größer die Zahlen werden, desto weniger Einfluss hat jede Konstante, sei sie noch so groß, wie Sie sich Spiele in Bezug auf die Laufzeit vorstellen können, wenn sie auch mit der Größe der Zahl, die Sie adressieren, schnell wächst.

Eine ganz besondere Barriere in Bezug auf die zeitliche Komplexität, die oft als Grenze zwischen praktisch machbar und einfach unmöglich angesehen wird, ist die sogenannte polynomial Laufzeit.

Das bedeutet nichts anderes, auch wenn die Laufzeit mit dem Wachsen drastisch anwachsen könnte n es ist immer noch möglich, dieses Wachstum mit a zu beschreiben Konstante Exponent kso dass die Laufzeit etwas herum ist n^k.

Andererseits ein Algorithmus ohne polynomial Die Laufzeit kann nicht mit irgendeinem Exponenten gemessen werden, wie groß Sie ihn auch machen möchten.

Um ein Beispiel zu geben, warum dieser Unterschied überhaupt von Bedeutung sein könnte, werfen wir einen Blick auf zwei imaginäre Algorithmen. Die erste mit polynomialer Laufzeit, sagen wir n^10 und nur ein anderes sagen Sie dieses mit Laufzeit n!.

Während es für kleine Zahlen nicht schlecht zu sein scheint, nehmen wir an, n ist nur 10, hier nimmt man den Algorithmus 10^10 = 10000000000 Zeiteinheiten während mit nur 3628800 Einheiten scheint unser zweiter Algorithmus noch viel schneller zu laufen.

Das Problem mit unserem zweiten Algorithmus ist, dass seine Laufzeit im Vergleich zu Algorithmus eins dramatisch schneller wächst. Bei n=100 du bekommst sowas wie: 100000000000000000000 für algorithm one ist es dabei schon so etwas wie 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 für Algorithmus zwei.

Grenzen noch weiter verschieben mit n=1000 wir enden mit: algorithm one at 1000000000000000000000000000000 während unser zweiter Algorithmus so etwas wie nimmt 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

Wenn Sie es nicht glauben, rechnen Sie einfach selbst nach. Das bc Handbuch enthält sogar ein Beispiel für die Implementierung der Fakultätsfunktion.

Aber nicht schwindelig werden beim Ziffernzählen… Es könnte interessant sein zu wissen, wie viele Nullen wir zu 10 hinzufügen müssten, um den Faktor zu erhalten, mit dem wir das Alter unseres Universums multiplizieren, um eine so große Spannweite zu erhalten Zeit, selbst wenn wir in Einheiten der Planck-Zeit gemessen haben. Ich weiß es leider nicht.

Das Interessante an all dem ist die Tatsache, dass es bis heute keinen bekannten Algorithmus gibt, der eine Faktorisierung durchführen kann polynomial Zeit.

Da es sich nicht nur um ein interessantes Forschungsgebiet an sich handelt praktisch Die Unmöglichkeit, große ganze Zahlen zu faktorisieren, spielt auch bei dem heute weit verbreiteten RSA-Public-Key-Verschlüsselungsalgorithmus eine wichtige Rolle, so dass auf diesem Gebiet fast schon viel geforscht wurde.

Algorithmen entdecken, die (ohne die bereits erwähnte Barriere zu durchbrechen) laufen leicht schneller als der Algorithmus, den Sie angenommen haben.

Da “Jim Balter” in seinem Kommentar bereits richtig kommentiert hat, lohnt sich vielleicht ein Blick in den referenzierten Artikel (siehe: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose), um einen Blick auf die Methoden zu werfen, die andere bereits entwickelt haben.

Dieser Artikel, der auch von “Jim” erwähnt wird, könnte eine weitere interessante Ressource sein: (siehe: Was ist der schnellste Faktorisierungsalgorithmus?)

Ein weiterer interessanter Link, den Sie sich ansehen sollten, ist die Liste der Gewinner der RSA-Factoring-Challenge der letzten Jahre, um sich ein Bild davon zu machen, wo die Grenze zwischen machbar und fast unmöglich heute liegt. (http://en.wikipedia.org/wiki/RSA_Factoring_Challenge)