Java Primfaktorzerlegung einer natürlichen Zahl anhand eines Algorithmus

[king0r]

Hallo,

ich habe die Aufgabe bekommen, eine beliebige natürliche Zahl in deren Primfaktoren zu zerlegen, beginnend mit dem kleinsten Faktor.
Der Algorithmus soll dabei alle Primfaktoren von n ermitteln und der Reihe nach ausgeben,
beginnend mit dem kleinsten Faktor.

Ich habe mir dazu bereits Gedanken gemacht in Form eines Ablaufplans:

int n
int divisor = 2

1. Lies Wert von Zahl n ein
2. Wenn n == 1
3. Dann gib „1“ aus
4. Sonst Wenn Zahl n == 0
5. Dann gib „0“ aus
6. Sonst Wenn Zahl >1
7. Wenn Zahl mod divisor == 0
8. Dann gib divisor aus
9. Sonst divisor = divisor + 1
11. Dann Zahl = Zahl / divisor
12. Sonst gib divisor = 1 aus
13. Fertig

Ich habe nun selbst einen Denklogikfehler, da ich nicht genau weiss, wie sich der Programmcode in java bei den fett markierten Bereichen verhält.

Allerdings funktioniert dieser Algorithmus nicht (glaube ich zumindest), wenn die natürliche Zahl andere Faktoren
> 2 enthält.

Ich bin den Ablaufplan mal mit der natürlichen Zahl 3 durchgegangen:
1. Zahl n = 3
2. 3 == 1? => falsch!
4. 3 == 0?=> falsch!
6. 3 > 1? =Y> wahr!
7. 3 mod 2 == 0? => falsch!

9. divisor = 2 + 1 = 3

So und ab da, weiss ich nicht was mein Ablaufplan dann machen würde? Springt er zu Zeile 11. oder wie von mir gewollt wieder in Zeile 6.?
Wenn er in Zeile 6 springen würde, wäre der Algorithmus schon mal vom Ansatz nicht verkehrt, oder?

Ich hoffe, dass sich hier nen guter Java Programmierer findet, der mir bei meinem Problem helfen kann.
Ich selbst bin leider, wie man auch merkt, völliger Anfänger und muss mich jetzt erstmal in die Materie exakt einarbeiten.

Danke schon mal!

 

[Stefan_Sch]

Woran hakts? An dem Algorithmus der Primfaktorzerlegung oder an der Implementierung in der Sprache Java?

 

[king0r]

Hy,

ich habe mich vll. oben echt etwas missverständlich augedrückt.

Primär geht es mir nur um den o.g. Algorithmus, dass der zumindest auf dem Blatt Papier einwandfrei durchläuft
Bin mir wie gesagt nicht sicher, ob ich alle Fehler abgefangen habe und der Algorithmus so überhaupt korrekt laufen würde.

Die Java Umsetzung folgt dann erst später.

Danke schon mal!

 

[Stefan_Sch]

Also ich hab irgendwie wenig Lust mich jetzt durch deinen Algorithmus zu wühlen, ich geh mir jetzt erstmal etwas in die Pfanne hauen.

Ansonsten verweise ich auf den Quadratischen Sieb (Quadratic Sieve) für die Faktorisierung von Primzahlen. Das ist das schnellste Verfahren, um die Primfaktoren einer Zahl mit weniger als 110 Dezimalstellen zu bestimmen.

http://de.wikipedia.org/wiki/Quadratisches_Sieb

http://www.nada.kth.se/~joel/qs.pdf

Implementierung, siehe

http://www.google.com/codesearch/p?...lic/Factor.java&q=Quadratic Sieve primes java

und

http://www.google.com/codesearch/p?...or/QuadAlg.java&q=Quadratic Sieve primes java

 

[king0r]

Bei der Aufgabenstellung hiess es explizit, dass auf keine implementierten Funktionen von java zurückgefriffen werden darf.

Zudem wäre es für mich sehr wichtig, zu wissen, ob der Algorithmus so passt. Nur so kann man aus seinen Fehlern lernen

 

[Stefan_Sch]

Bei der Aufgabenstellung hiess es explizit, dass auf keine implementierten Funktionen von java zurückgefriffen werden darf.

Deshalb führen auch die ersten Hyperlinks auf die theoretischen Grundlagen des Quadratischen Siebes. Lediglich die letzten beiden Links führen zu einer Implementierung in Java.

Zudem wäre es für mich sehr wichtig, zu wissen, ob der Algorithmus so passt. Nur so kann man aus seinen Fehlern lernen

Soll das Marke Eigenbau sein? Keine Ahnung was du da für einen Algorithmus erarbeitet hast. Das Ganze sieht nach einem primitiven linearen Algo aus, der auf den Modulo Operator zurückgreift. Ehrlich gesagt habe ich mir die paar Zeilen überhaupt nicht angesehen.

 

[king0r]

Jo klar ist meiner Marke Eigenbau, aber prinzipiell sollte er es doch so auch tun? Allerdings gibt es noch, soweit ich das nachvollziehen kann, Probleme bei den beiden Wenn Schleifen.
Sprich, wenn der divisor >2 ist, wird dieser von meinem Algo nicht ausgegeben. Das müsste ich noch auf die Reihe kriegen, nur ich weiss net so recht, wie.

 

[Stefan_Sch]

Also um mal eines klar zu stellen. Für die Primfaktorzerlegung gibt es nicht den perfekten Algorithmus mit einer guten Komplexität, sonst könnte man nämlich den RSA und andere Public-Key-Chiffre wegwerfen.

Dein oben angegebener Algorithmus ist falsch und wird sicherlich nicht funktionieren. Er zerlegt die Zahl nämlich nicht in ihre Primfaktoren, weil er überhaupt nicht überprüft, ob die nächste Zahl eine Primzahl ist. Stattdessen zählst du in einer Schleife den Divisor einfach um 1 hoch.

Ich habe dir mit dem Quadratisches Sieb bereits einen allgemein anerkannten Algorithmus für die Primfaktorzerlegung genannt.

Wenn du diesen nicht verwenden willst, dann musst du eben einen eigenen trivialen Algorithmus verwenden. Dieser hat eine lausige Komplexität, aber er ist einfach.

Ich bin so frei dir bei diesem einfachen Algorithmus zu helfen.

Solange Zahl > 1
    i = 2
    Solange Zahl % i nicht 0 [U]und[/U] i nicht Primzahl
        i = i + 1
    Ausgabe von i
    Zahl = Zahl / i
Ende