Primfaktorzerlegung

Monty31

Mitglied
Hallo zusammen,
ich habe bei der folgende Aufgabe Probleme. Ich hoffe,dass einer von euch mir hier helfen kann.
Erstellen Sie dazu eine Datei Algebra.java mit einer gleichnamigen Klasse, die die folgenden
drei statischen Klassenmethoden öffentlich bereitstellt ( public static ):
a) Die Methode long[][] primfaktorzerlegung(long n) ermittelt die Primfaktorzerle-
gung ihres Arguments n und gibt sie so als 2-dimensionales Feld z zurück, dass:
n = p 0 ^e 0 · p 1 ^e 1 · p 2^ e 2 · . . . · p k−1 ^e k−1
wobei z[0] = {p 0 , p 1 , p 2 , . . . , p k−1 } die sortierten (p 0 < p 1 < p 2 < . . . < p k−1 ) Primfaktoren sowie z[1] = {e 0 , e 1 , e 2 , . . . , e k−1 } ihre jeweiligen Potenzen (e i > 0) sind.
Wie auch im öffentlichen Testfall festgelegt, ist die Primfaktorzerlegung für n = 1 das leere
Produkt (also je ein leeres Unterfeld, aber eben nicht null )!

b) Die Methode long ggT(aPFZ, bPFZ) bekommt die Primfaktorzerlegungen aPFZ bzw.
bPFZ zweier Zahlen a und b in obiger Feld-Darstellung und soll deren größten gemeinsa-
men Teiler ggT (a, b) berechnen.

c) Die Methode long kgV(a, b) soll das kleinste gemeinsame Vielfache kgV (a, b) zweier
long -Zahlen a und b berechnen und zurückgeben.
 

Monty31

Mitglied
Bei der Teilaufgabe a). Ich verstehe es als Programmieranfänger nicht was da verlangt wird oder wie ich es in Java Code umsetzen kann.:(
 

mihe7

Top Contributor
Naja, es ist Sinn und Zweck der Sache, dass Du Dich mit dem Thema auseinandersetzen musst.

Machen wir mal drei Schritte daraus:

1. Wie würdest Du denn die Primfaktoren ohne Java-Code ermitteln?
2. Kannst Du dafür einen Algorithmus angeben?
3. Kannst Du den Algorithmus nach Java übersetzen?
 

mihe7

Top Contributor
OK, warum kommst Du von 2*2*9 auf 2*2*3*3? Überleg Dir das mal an verschiedenen Beispielen. Da steckt eine gewisse Logik dahinter.

Nachtrag: wie kommst Du von 36 auf 2*18?
 

mihe7

Top Contributor
Anders gefragt: Du hättest ja auch statt mit 2*18 mit 3*12 anfangen können, warum hast Du das nicht gemacht? Das hat einen Grund.
 

mihe7

Top Contributor
Vielleicht brauchst Du auch nochmal ein anderes Beispiel: wie würdest Du bei der Zerlegung von 126 vorgehen?
 

mihe7

Top Contributor
Wir kommen der Sache näher :) Halten wir mal fest:
1. Mit der 2 fängst Du an.
2. Die 2 ist ein Sonderfall, alle anderen Primzahlen sind ungerade.

Wie prüfst Du jetzt, ob die 2 ein Primfaktor ist?
 

mihe7

Top Contributor
Nein, das wäre die Prüfung, ob die 2 eine Primzahl ist. Was muss aber gelten, damit die 2 Primfaktor der Zerlegung einer anderen Zahl ist?
 

mihe7

Top Contributor
Aha! Umgekehrt gilt dann natürlich, dass eine Primzahl p Teil der Primfaktorzerlegung einer anderen Zahl z ist, wenn ...
 

mihe7

Top Contributor
Geht doch :)

Du beginnst also mit der ersten Primzahl p, schaust nach ob die gegebene Zahl z durch p teilbar ist. Falls ja, dann ist p Teil der PFZ von z.

Um Dein Beispiel aufzugreifen: 36 / 2 = 18, also teilbar durch 2 => 2 kommt in der PFZ bislang einmal vor.

Wie geht es weiter?
 

mihe7

Top Contributor
Nicht so schnell. Alles einzeln machen:
Code:
36/2 = 18 => 2 teilt die 36 => 2 ist Primfaktor (das 1. Mal)
18/2 = 9 => 2 teilt die 18 => 2 ist Primfaktor (das 2. Mal)
9 / 2 = 4,5 => 2 teilt die 9 nicht
An der Stelle überlegst Du Dir, dass es keinen Sinn mehr hat, mit der 2 weiter zu machen. Also nimmst Du die 3.
Code:
9 / 3 = 3 => 3 teilt die 9 => 3 ist Primfaktor (das 1. Mal)
3 / 3 = 1 => 3 teilt die 3 => 3 ist Primfaktor (das 2. Mal)
An der Stelle ist nur noch die 1 übrig. Es kann also keinen weiteren Primfaktor geben => PFZ fertig.

Gleich noch mehr dazu.
 

mihe7

Top Contributor
Du kannst den Spaß jetzt mal allgemein für eine Zahl z formulieren:
Code:
1. Wir beginnen mit einer leeren PFZ und einem möglichen Primfaktor p := 2
2. So lange z durch p teilbar ist, schreiben wir p zur PFZ "dazu" und setzen z := z/p
3. Falls z > 1 muss es weitere Primfaktoren geben. Wir wählen p := nächster Kandidat und machen mit Schritt 2 weiter.
4. Wir geben PFZ aus. Fertig.
Das wäre ein erster Ansatz für einen Algorithmus. Hier stellt sich insbesondere die Frage, was man als nächsten Kandidaten wählt. Was würdest Du sagen?
 

mihe7

Top Contributor
Schau Dir mal den Algorithmus an, da steht doch wähle p := nächster Kandidat. Du musst allgemein formulieren, was Du als nächsten Kandidaten wählen würdest. Mal vier Möglichkeiten zur Auswahl:
1. die nächste Zahl
2. die nächste gerade Zahl
3. die nächste ungerade Zahl
4. die nächste Primzahl
Was würdest Du als nächsten Kandidaten wählen und warum?
 

httpdigest

Top Contributor
Überlege nochmal, warum es PRIMFAKTORzerlegung heißt.
Es wird z.B. keine Zahl geben, die die PRIMFAKTOREN 2 * 3 * 4 besitzt. In dem Fall wäre es 2 * 2 * 2 * 3.
 

DrZoidberg

Top Contributor
Die nächste ungerade Zahl, die ein Teiler von z ist, musst automatisch auch eine Primzahl sein. Denn wenn es keine wäre, müssten Primfaktoren existieren, die kleiner als p sind. Die kann es aber nicht geben, da sie schon alle raus dividiert worden sind.
 

mihe7

Top Contributor
Das wäre die intuitiv richtige Antwort :) Denn: eine gerade Zahl > 2 kann kein Primfaktor sein.

Es wäre allerdings nicht besonders effizient, die nächste Primzahl zu verwenden, denn Du müsstest diese erst ermitteln, was relativ aufwändig ist. Daher macht man es so, wie @DrZoidberg es schon geschrieben hat: man nimmt einfach die nächste ungerade Zahl.

Den Algorithmus kann jetzt mal ein wenig umschreiben:
Code:
1. setze fz := ""
2. setze p := 2
3. so lange z > 1 wiederhole:
4.     falls gilt p teilt z:
5.         füge p zu fz hinzu
6.         z := z / p
7.     sonst
8.         p := nächsteUngeradeZahl(p)
9. gib fz aus

Jetzt mal eine Aufgabe für Dich: versuch das als Java-Programm zu formulieren.
 

httpdigest

Top Contributor
Als nächste Optimierung/Ausbaustufe kannst du dir ja mal das Sieb des Eratosthenes angucken. Es erfordert einen Speicherbereich der Größe Ω(√n) und erlaubt es dir, weniger Zahlen zu testen als immer wieder nur jede ungerade Zahl. Im Endeffekt ändert sich damit also `p := nächsteUngeradeZahl(p)` zu `p := nächsteNichtGefilterteZahl(p)`.
 

DrZoidberg

Top Contributor
Versuch mal den Code von mihe7 Zeile für Zeile nach Java zu übersetzen. Wenn du bei einer Zeile nicht weiter weißt, dann frag nochmal nach.
 

mihe7

Top Contributor
Kannst Du vorübergehend mal einfach mit
Code:
fz = fz + p + " ";
machen. Für die Aufgabe selbst muss man das eh noch anpassen.
 

Neue Themen


Oben