•  18-09-2019
  •  | 
  •  

Frage

Ich versuche, ein Programm zu schreiben, das größte Primfaktor von einer sehr großen Zahl zu finden, und habe mit unterschiedlichem Erfolg verschiedene Methoden ausprobiert. Alle die, die ich bisher unglaublich langsam gefunden haben. Ich hatte einen Gedanken, und frage mich, ob dies ein gültiger Ansatz ist: 

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Dieser Ansatz würde eine Eingabe nehmen, und würde wie folgt vor:

200 -> 100 -> 50 -> 25 -> 5 (Rückkehr)

90 -> 45 -> 15 -> 5 (Rückkehr)

Er teilt currentNum wiederholt durch die kleinste teilbare Zahl (meist 2 oder 3), bis currentNum selbst eine Primzahl ist (es gibt keine teilbare Primzahl kleiner als die Quadratwurzel von currentNum) und übernimmt dies der größte Primfaktor der ist Original-Eingang.

Wird das immer? Wenn nicht, kann mir jemand ein Gegenbeispiel?

-

EDIT:. Durch die sehr groß, ich meine etwa 2 ^ 40 oder 10 ^ 11

War es hilfreich?

Lösung

Das wird immer wegen der Einzigartige Primfaktorzerlegung Satz arbeiten.

Andere Tipps

Die Methode funktioniert, wird aber langsam sein. „Wie groß sind Ihre Zahlen?“ bestimmt das Verfahren zu verwenden:

Sicherlich wird es funktionieren ( Mark Byers' Antwort sehen), aber für „sehr groß“ Eingänge kann es viel zu lange dauern. Sie sollten beachten, dass Ihr Anruf getLowestDivisiblePrimeNumber() eine weitere Schleife verdeckt, so dass dies läuft auf O (N ^ 2), und dass je nachdem, was Sie unter „sehr groß“ kann es auf bignums , die langsam sein.

Sie könnte es beschleunigen ein wenig, mit der Feststellung, dass Ihr Algorithmus nie Faktoren kleiner als die letzte gefunden überprüfen muss.

Sie versuchen, die Primfaktoren einer Zahl zu finden. Was Sie vorschlagen, funktionieren wird, aber immer noch für eine große Zahl langsam sein .... sollten Sie dafür dankbar sein, da die meisten modernen Sicherheit dies ist ein schwieriges Problem ausgesagt wird.

Von einer schnellen Suche nur ich, die schnellsten bekannte Art und Weise eine Reihe zu Faktor ist durch die Elliptische-Kurven-Methode.

Sie könnten versuchen, Ihre Nummer bei dieser Demo werfen: http://www.alpertron.com .ar / ECM.HTM .

Wenn das Sie überzeugt, könnten Sie versuchen, entweder den Code zu stehlen (das ist kein Spaß, bieten sie einen Link zu ihnen!) Oder auf der Theorie der es an anderer Stelle zu lesen auf. Es gibt einen Wikipedia-Artikel über sie hier: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization aber ich bin zu dumm, es zu verstehen. Zum Glück, es ist dein Problem, nicht meins! :)

Die Sache mit Project Euler ist, dass es in der Regel eine offensichtliche Brute-Force-Methode, das Problem zu tun, das nur etwa ewig dauern wird. Da die Fragen schwieriger geworden, müssen Sie clevere Lösungen implementieren.

Eine Möglichkeit, dieses Problem lösen können, ist eine Schleife zu verwenden, die die kleinste (positive ganze Zahl) Faktor einer Zahl immer findet. Wenn der kleinste Faktor eine Zahl, die Zahl ist, dann haben Sie den größten Primfaktor gefunden!

Detaillierte Programmbeschreibung:

Sie können dies tun, indem Sie drei Variablen zu halten:

Die Zahl, die Sie zu Faktor versuchen (A) Ein Stromteilerspeicher (B) Ein größter Teiler Speicher (C)

Zunächst lassen (A) die Anzahl der Sie interessiert sind - in diesem Fall ist es 600851475143. Dann lassen (B) sein 2. eine bedingte haben, die überprüft, ob (A) teilbar durch (B). Wenn es teilbar ist, teilt (A) durch (B), Reset (B) bis 2, und gehen Sie zurück zu überprüfen, ob (A) ist teilbar durch (B). Sonst, wenn (A) nicht teilbar durch (B) ist, Inkrementieren (B) um +1 und dann prüfen, ob (A) teilbar durch (B). Führen Sie die Schleife, bis (A) 1. Die (3) Sie zurückkommen wird der größte Primfaktor von 600.851.475.143 sein.

Es gibt zahlreiche Möglichkeiten, dies effektiver machen könntest - statt auf die nächste ganze Zahl von Inkrementieren Sie auf den nächsten unbedingt Primzahl erhöhen könnten, und stattdessen ein größtes Teiler Geschäft zu halten, könnten Sie einfach die aktuelle Nummer zurück, wenn sein nur Teiler selbst ist. Allerdings läuft der Algorithmus, den ich oben beschrieben in Sekunden unabhängig.

Die Implementierung in Python ist wie folgt: - 

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Beispiel: Lassen Sie sich den größten Primfaktor von 105 finden Sie das oben beschriebene Verfahren mit

.

Es sei (A) = 105 (B) = 2 (wir beginnen immer mit 2), und wir keinen Wert für (C) noch.

Sie (A) teilbar durch (B)? Nr Erhöhungsschritte (B) von 1: (B) = 3. Sind I (A) teilbar durch (B)? Ja. (105/3 = 35). Der größte Divisor gefunden, so weit ist 3. Sei (C) = 3. Aktualisieren (A) = 35. Reset (B) = 2.

Nun ist (A) teilbar durch (B)? Nr Erhöhungsschritte (B) von 1: (B) = 3. Ist (A) teilbar durch (B)? Nr Erhöhungsschritte (B) von 1: (B) = 4. Ist (A) teilbar durch (B)? Nr Erhöhungsschritte (B) von 1: (B) = 5. Ist (A) teilbar durch (B)? Ja. (35/5 = 7). Der größte Teiler wir bisher gefunden wird in (C) gespeichert. (C) ist derzeit 3. 5 größer als 3 ist, so aktualisieren wir (C) = 5. Wir aktualisieren (A) = 7. Wir zurückgesetzt (B) = 2.

Dann wiederholen wir den Prozess für (A), aber wir halten Inkrementieren (B) nur bis (B) = (A), weil 7 Primzahl ist und hat keine Teilern anderes als sich selbst und 1. (Wir konnten bereits stoppen wenn (B)> ((A) / 2), da Sie nicht integer Teilern größer als die Hälfte einer Zahl haben können - die kleinsten möglichen Teiler (außer 1) nach Nummer 2)

So an diesem Punkt kehren wir (A) = 7.

Versuchen Sie, ein paar von ihnen von Hand zu tun, und du wirst den Dreh der Idee

erhalten
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top