Rekursive Primfaktorzerlegung

[zwigglewiggle]

Hallo,
ich habe von der uni eine Aufgabe, in der verlangt wird, dass man einen rekursiven algorithmus zur ermittlung der primfaktorzerlegung einer Natürlichen Zahl schreiben soll.
Leider fehlt mir komplett der Ansatz wie man so etwas implementieren kann(da wir keine schleifen oder klassen der Java API verwenden dürfen)
wäre über jede Hilfe/denkanstoß dankbar

 

[LimDul]

Gar keine Schleifen?

Was heißt Ermittlung? Sollen die einfach ausgegeben werden?

 

[zwigglewiggle]

ne garkeine schleifen und auch keine klassen aus der java api
ja sie sollen in einer liste gespeichert und zurückgegeben werden(die Liste ist ebenfalls ein selbst erstellter datentyp)

 

[kneitzel]

Fangen wir doch einfach erst einmal beim ersten Schritt an:
Wie zerlegt man eine Zahl in Primfaktoren? Kannst Du das? Wie machst Du das? Kannst Du den Ablauf GENAU beschreiben, so dass dies jeder machen kann - auch wenn er gar keine Ahnung hat, was da überhaupt passiert?

Das wäre ein erster Schritt. Wenn man den hat, dann kann man sich überlegen, wie man den rekursiv lösen könnte ...

 

[zwigglewiggle]

naja im normalfall würde ich um eine beliebege zahl x zu zerlegen erst schauen ob sie durch 2 teilbar ist, dann wär das der erste primfaktor.
falls dies nicht der fall ist würde ich es mit 3 probieren usw.
wenn ich einen primfaktor gefunden habe würde ich x/faktor1 teilen und das ganze mit dem ergebnis wiederholen

 

[mihe7]

und das ganze mit dem ergebnis wiederholen

Womit Du Deine Rekursion hättest Wann musst Du aufhören?

 

[zwigglewiggle]

wenn das letzte ergebnis selbst eine primzahl ist ?

 

[kneitzel]

Wobei das nicht ausführlich genug ist. Gewöhn Dir da an, wirklich genau zu formulieren! Ansonsten rennst Du bei der Umsetzung in Probleme, weil da dann die Feinheiten schwerer zu erkennen sind...

Du hast also X ... prüfst, ob die Zahl durch 2 teilbar ist.
Ist dies nicht der Fall, dann prüfst Du X mit der 3 ...
Ist es der Fall, dann ist 2 eine zu merkende Primzahl der Zerlegung. Und du machst weiter mit X/2 und 2.

Abbruch ist von mir aus, wenn die übergebene Zahl 1 ist ...

Man erkennt nun zum einen:
a) Die Rekursion (Wobei du halt mit X / teiler+1 oder x/teiler, teiler weiter machst)
b) Was gebraucht wird: X, der aktuelle Teiler und die Liste der Primzahl-Faktoren.
c) Ein Abbruchkriterium (X == 1)

Das lässt sich natürlich noch optimieren, aber das wäre ein erster Ansatz.

wenn das letzte ergebnis selbst eine primzahl ist ?

Woher weisst Du das? Willst Du jede Zahl erst prüfen?

 

[mihe7]

Was gebraucht wird: X, der aktuelle Teiler

Der Teiler wird nicht benötigt, da man immer von vorne beginnen muss.

EDIT: war Hirnkrampf. Vergiss es.

 

[mw1304]

Hi zwigglewiggle,
du belegst wahrscheinlich auch AuD an der FAU. Wie kommst du drauf,dass man keine Schleifen verwenden darf? Steht so nicht in der Aufgabenstellung