# Primfaktorzerlegung



## Monty31 (11. Nov 2018)

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.


----------



## mihe7 (11. Nov 2018)

Monty31 hat gesagt.:


> ich habe bei der folgende Aufgabe Probleme.


An welcher/n Stelle/n konkret?


----------



## Monty31 (11. Nov 2018)

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 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

1. Als Beispiel die Zahl 36.
Primfaktorzerlegung davon: 2 * 18 -> 2 * 2 * 9 -> 2 * 2 * 3 * 3
Aber Algorithmus davon kann ich nicht.


----------



## mihe7 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

Weil die 9 das Ergebnis von 3^2 bzw. 3 * 3 ist.


----------



## mihe7 (11. Nov 2018)

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 (11. Nov 2018)

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


----------



## Monty31 (11. Nov 2018)

Achso die 2 ist ja eine Primzahl und zwar die einzige gerade Primzahl oder?


----------



## mihe7 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

Die zwei ist durch 1 und durch sich selbst teilbar


----------



## mihe7 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

Da habe ich keine Ahnung


----------



## mihe7 (11. Nov 2018)

Hallo?!? Du kannst mir doch sofort sagen, dass die 2 kein Primfaktor von 15 sein kann, weil...


----------



## Monty31 (11. Nov 2018)

Weil 15 nicht durch 2 teilbar ist.


----------



## mihe7 (11. Nov 2018)

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


----------



## Monty31 (11. Nov 2018)

wenn z durch p teilbar ist .


----------



## mihe7 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

Dann 18 durch 2 = 9 -> 2*2*9.
9 ist nicht durch 2 teilbar, aber durch 3, d.h. 2*2*3*3=36


----------



## mihe7 (11. Nov 2018)

Nicht so schnell. Alles einzeln machen:

```
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.

```
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.


----------



## Monty31 (11. Nov 2018)

Achso ok.


----------



## mihe7 (11. Nov 2018)

Du kannst den Spaß jetzt mal allgemein für eine Zahl z formulieren:

```
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?


----------



## Monty31 (11. Nov 2018)

Die 3 .


----------



## mihe7 (11. Nov 2018)

Wenn Du immer die 3 nimmst, kommst Du nicht weit


----------



## Monty31 (11. Nov 2018)

sondern


----------



## DrZoidberg (11. Nov 2018)

Erst 2, dann 3 und danach erhöhst du p immer solange um 2, bis z durch p teilbar ist.


----------



## mihe7 (11. Nov 2018)

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?


----------



## Monty31 (11. Nov 2018)

Ich wurde sagen die nächste Zahl, weil man jede zahl einmal durch gehen muss.


----------



## httpdigest (11. Nov 2018)

Überlege nochmal, warum es *PRIMFAKTOR*zerlegung 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.


----------



## Monty31 (11. Nov 2018)

Achso die nächste Primzahl.


----------



## DrZoidberg (11. Nov 2018)

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 (11. Nov 2018)

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:

```
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 (11. Nov 2018)

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)`.


----------



## Monty31 (11. Nov 2018)

Ich verstehe es einfach nicht, wie ich es in Java Programm formulieren soll.


----------



## DrZoidberg (11. Nov 2018)

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.


----------



## Monty31 (11. Nov 2018)

Was heißt "setze" in Java übersetzt?


----------



## DrZoidberg (11. Nov 2018)

Eine Variable auf einen Wert setzen, geht in Java mit "=" z.B. fz = "";


----------



## Monty31 (11. Nov 2018)

und hinzufügen?


----------



## mihe7 (11. Nov 2018)

Kannst Du vorübergehend mal einfach mit 
	
	
	
	





```
fz = fz + p + " ";
```
 machen. Für die Aufgabe selbst muss man das eh noch anpassen.


----------

