• Wir präsentieren Dir heute ein Stellenangebot für einen Java Entwickler - m/w/d in Augsburg, München, Stuttgart oder Bamberg. Hier geht es zur Jobanzeige

Rekursive Primfaktorzerlegung

zwigglewiggle

zwigglewiggle

Mitglied
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 :)
 
Zuletzt bearbeitet:
L

LimDul

Top Contributor
Gar keine Schleifen?

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

zwigglewiggle

Mitglied
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

kneitzel

Top Contributor
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

zwigglewiggle

Mitglied
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
 
kneitzel

kneitzel

Top Contributor
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?
 
M

mw1304

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

Ähnliche Java Themen

Anzeige

Neue Themen


Oben