Wie alle die Primfaktoren in einem unsigned long long integer zu finden?

Question

Ich habe eine Zuordnung alle Primfaktoren einer Zahl zu finden ...

Ich brauche eine Funktion zu schreiben, die eine Zahl nimmt und sagt mir, alle die Primfaktoren der Zahl. Zum Beispiel:

• n = 350 Primfaktoren: 2 5 5 7

(I übergeben an die Funktion eine Zahl im Bereich von 0 bis 18446744073709551615 - Die maximale Anzahl größte Zahl ist, die passt in eine 64-bit unsigned long long integer).

Answer 1

Das ist ein schwieriges Problem, und einer der Hauptgründe für die ganze Erforschung von Quantencomputern. Schauen Sie sich auf Shor-Algorithmus . Einfache Brute-Force ohne Optimierungen etwas wie 1000 Jahre dauern würde, obwohl in diesem speziellen Fall (64-Bit-Integer), sollten Sie in der Lage sein, Ihre Laufzeit auf wenige Minuten zu reduzieren.

Unter der Annahme, haben Sie einen trivialen Fall von (höchstens) einem großen Primfaktor, können Sie erheblich beschleunigen, indem Sie etwas zu tun, wie von 2 bis zu zählen und zu versuchen, jede Zahl (mehrere Male, wenn es funktioniert; 12 2 sein würde, 2, und 3 zum Beispiel). Nachdem Sie einen Faktor finden, reduzieren Sie Ihre Zielnummer um diesen Faktor und testen, ob das neue Ziel Primzahl ist.

weiter zu beschleunigen, können Sie die Verarbeitung über mehrere Threads zu tun, mit jedem verantwortlich für eine Reihe von Teilern. Sie könnten primality Tester auf einem oder mehr Threads, die Bereitstellung Primzahlen zum Test Thread ausgeführt, so dass Sie nur zu dividieren durch Primzahlen versucht werden.

Sie könnten sogar von der Spitze des Bereichs nach unten suchen, wenn Sie die Person denken, den Wert bereitstellt versucht tricksome zu sein, obwohl mit der Dichte der Primzahlen ist, so viel höher am unteren Ende, dies wird wahrscheinlich nicht helfen .

Die wichtigste Sache zu erinnern, aber, dass der größtmöglichen Faktor X, außer für X selbst, ist die Quadratwurzel von X. Jedes Mal, wenn Sie einen Faktor finden, die möglichst großen verbleibende Faktor deutlich verringert.