Was wäre ein geeigneter Algorithmus, um Zahlen im Bereich von einigen Milliarden zu faktorisieren?

Ich lerne gerade Python und um mir Gründe zu geben, das anzuwenden, was ich lerne, habe ich einen Riss bei einigen Problemen in Project Euler

Ich bin derzeit auf Nummer 3, die den höchsten Primfaktor dieser Nummer bestimmen soll.

Ich habe festgestellt, dass ich wahrscheinlich zwei Algorithmen haben muss, einen zur Bestimmung der Primalität und den zweiten, bei dem Faktoren der Zahl gefunden werden müssen.

Also habe ich über Wiki- Artikel gelesen . Versuchen Sie herauszufinden, welcher Algorithmus am besten geeignet ist und wie Sie vorgehen müssen.

Aber es ist schon eine Weile her, dass ich einige Hardcore-Mathematik-basierte Programmierungen gemacht habe und ich habe Mühe, irgendwo anzufangen.

Ich habe versucht, die Faktorisierungsmethode von Fermat unter Einbeziehung von Trial by Division zu verwenden, aber ich möchte nichts zu kompliziert machen. Ich möchte nicht RSA knacken. Ich möchte nur zwei Algorithmen, die für mein Problem geeignet sind, und da liegt meine Frage.

Welche Algorithmen würden Sie zum Testen der Primalität / zum Faktorisieren einer Zahl verwenden, die für das jeweilige Problem geeignet ist?

Bearbeiten

Ich danke Ihnen allen für Ihre Antworten und Erkenntnisse, die am hilfreichsten waren. Ich habe alle, die nützlich waren, entweder durch Ratschläge oder durch eigene Euler-Erfahrungen bewertet. Das, das ich als richtig markiert habe, war einfach das nützlichste, da es mir einen geeigneten Ausgangspunkt gab, von dem aus ich in die richtige Richtung schob. Nochmals vielen Dank =)

Mein Ansatz für diese Probleme ist normalerweise der folgende: Erstellen Sie den einfachsten möglichen Algorithmus, um ihn zu lösen. Dies ist normalerweise ein Brute-Force-naiver Ansatz, und testen / berechnen Sie dann mathematisch, ob er zu langsam ist oder nicht. Meistens ist es gut genug. Wenn dies nicht der Fall ist, haben Sie einen klaren Ausgangspunkt, an dem Sie arbeiten und die Dinge optimieren können, bis der Algorithmus effizient genug ist.

Hier ist ein einfacher Algorithmus zur Lösung von Problem 3 in Project Euler (in C, aber die Übersetzung in Python sollte trivial sein):

#include <stdio.h>
#include <math.h>

int isPrime(int n){
    int i;

    if (n==2)
        return 1;

    if (n%2==0)
        return 0;
    for (i=3;i<sqrt(n);i+=2)
        if (n%i==0)
            return 0;
    return 1;
}

int main(){
    long long int n = 600851475143;
    int i = 3;

    while (i<50000){
        if (isPrime(i))
            if (n%i==0)
                printf("%d\n",i);
        i+=2;
    }
    return 0;
}

Es lohnt sich, Code zu schreiben, der Faktorisierung und Prim-Finding (im Grunde dasselbe) bewirkt, da Sie ihn wahrscheinlich in vielen anderen Euler-Fragen wiederverwenden werden. Sie können den Code für spätere Fragen verbessern und möglicherweise nicht erschöpfende Primalitätstests prüfen, wenn Sie feststellen, dass er nicht mehr effizient genug ist. Daher schlage ich vor, dass der derzeit einfachste Ansatz darin besteht, Folgendes zu tun:

• Schreiben Sie eine einfache Schleife, die alle Primzahlen findet (dh testen Sie für jede Zahl ihre Teilbarkeit durch jede zuvor gefundene Primzahl und fügen Sie sie der Liste der Primzahlen hinzu, wenn alle fehlschlagen).
• Versuchen Sie, die Zahl, die Sie faktorisieren möchten, durch jede Primzahl bis zur Quadratwurzel der Zahl zu teilen.

Tatsächlich ist dies ein Bereich aktiver Forschung in Mathematik und Informatik. Der Wikipedia-Artikel gibt einen guten Überblick:

http://en.wikipedia.org/wiki/Integer_factorization

Wählen Sie einen beliebigen Algorithmus aus, den Sie mögen / interessant finden, und probieren Sie ihn aus.

Sie müssen wahrscheinlich einen Kompromiss eingehen: Die meisten "guten" Algorithmen erfordern einiges an mathematischem Hintergrund, um wirklich zu verstehen (obwohl Sie sie implementieren könnten, ohne sie vollständig zu verstehen).

Wenn Sie nicht wissen, wo Sie anfangen sollen, würde ich das quadratische Sieb empfehlen:

http://en.wikipedia.org/wiki/Quadratic_sieve

Es erfordert keine wahnsinnigen mathematischen Kenntnisse, funktioniert aber gut.

Ich habe vor einiger Zeit einige ProjectEuler-Probleme in Ruby mithilfe der Testteilung mit Primzahlen gelöst .

Ich fand, dass das Erzeugen der Primzahlen weitaus kritischer war als der eigentliche Faktorisierungsalgorithmus. Sobald ich meinen naiven Ansatz zur Generierung von Primzahlen durch ein Sieb ersetzte, verringerten sich meine Ausführungszeiten auf einen angemessenen Betrag.

Ganz einfach ...

Finden der Faktoren von X: Ich würde (n) bei 2 beginnen und bis zur ganzen Zahl (Boden, nicht rund) der Quadratwurzel von X arbeiten. Wenn das Teilen von X durch n Y ergibt, ist Y eine ganze Zahl, sowohl n als auch Y sind Faktoren. Die niedrigsten Werte von n ergeben die höchsten Werte von Y.

Primalität von Y: Wiederholen Sie die Schleife (m) von 2 bis zur Quadratwurzel von Y und prüfen Sie, ob Y / m eine ganze Zahl ist. Wenn dies der Fall ist, ist Y keine Primzahl. Gehen Sie zurück, um einen anderen Faktor zu finden.

Wenn m die Wurzel von Y trifft, haben Sie Ihre Primzahl. Hör auf zu schauen. Y ist die Antwort.

Wenn n die Wurzel von X trifft, gibt es keine Primfaktoren.

Da es bereits eine vollständige Lösung gibt, werde ich diese Haskell veröffentlichen ...

--  Problem is to find the largest prime factor of 600851475143
module Factor (testval, bigfactor) where
  testval = 600851475143

  bf' :: Integer -> Integer -> Integer

  bf' f x | (f == x)         = f
          | ((mod x f) == 0) = bf' f (div x f)
          | True             = bf' (f+1) x

  bigfactor :: Integer -> Integer

  bigfactor x | (x <  1) = error "Parameter less than 1"
              | (x == 1) = 1
              | True     = bf' 2 x

Grundsätzlich besteht keine Notwendigkeit, die Primalität zu testen. Wenn Sie die gefundenen Faktoren aufteilen (und sicherstellen, dass Sie mit sich wiederholenden Faktoren umgehen), kann ein Nicht-Prim-Faktor niemals auftreten, da ein Nicht-Prim-Faktor ein Produkt kleinerer Prim-Faktoren ist.

Geladen und ausgeführt mit GHCi - es ist sofort und ich habe jetzt insgesamt 4 (ja, vier!) Euler-Probleme gelöst.

Ich baue auch mein Python-Wissen auf und beantworte auch die Probleme von Project Euler in meinem Github-Repo: https://github.com/rentes/Euler .

Für Problem 3 habe ich eine einfache Lösung programmiert, die auf folgenden Prämissen basiert:

1) Wenn eine positive ganze Zahl n gegeben ist, beginne ich, sie durch 2, 3, ..., m zu teilen, und wenn ich feststelle, dass m ein Primfaktor ist, füge ich sie einer Liste hinzu. Ich füge der Liste nicht ein Vielfaches bereits entdeckter Primfaktoren hinzu. Zum Beispiel ist 4 ein Vielfaches von 2, sodass 4 nicht zu dieser Liste hinzugefügt wird.

2) Ich multipliziere dann jede Primzahl auf der Liste, um zu sehen, ob sie gleich n ist. Wenn gleich, haben wir alle Primfaktoren von n gefunden. Wenn nicht, teilen Sie n weiter durch die nächste m-Zahl, bis die Mutifizierung aller Primfaktoren gleich n ist oder m n erreicht.

Weitere Informationen finden Sie unter https://github.com/rentes/Euler/blob/master/problem3.py . Ich habe Kommentare hinzugefügt, die Ihnen helfen, zu verstehen, was ich programmiert habe. Es ist eine einfache Lösung, und ich bin sicher, dass es nicht die schnellste Lösung ist, aber es funktioniert und es ist einfach genug zu verstehen.

Freundliche Grüße