# dynamisches Array für Primfaktorzerlegung



## scandic (16. Jan 2011)

Hallo, mir kam gestern in den Sinn einen Algorithmus zu schreiben, der das kgV (kleinstes gemeinsames Vielfaches) aus 2 oder mehr Zahlen berechnen kann. Dazu benötige ich zuerst einen Teilalgorithmus, mit dem ich eine Zahl in ihre Primfaktoren zerlegen kann. Dies läuft menschengemacht so ab (Beispiel 75):
Ist 75 durch 2 (als kleinste Primzahl) teilbar? Nein!
Ist 75 durch 3 teilbar? Ja!
75/3 = 25
(Der erste Primfaktor ist also 3)
Ist 25 durch 3 teilbar? Nein!
Ist 25 durch 5 teilbar? Ja!
25/5 = 5
5 ist eine Primzahl.
Damit ergibt sich folgendes Ergebnis:
3*5*5 = 75

Aber wie kriege ich in Java jetzt ein Array realisiert, dass dynamisch mitwächst? Muss ich mir ein Array definieren, dass vllt. 1000 Werte speichert und dann nur die ersten x belegen?

Danke im voraus für eure Hilfe,
scandic


----------



## eRaaaa (16. Jan 2011)

scandic hat gesagt.:


> Aber wie kriege ich in Java jetzt ein Array realisiert, dass dynamisch mitwächst? Muss ich mir ein Array definieren, dass vllt. 1000 Werte speichert und dann nur die ersten x belegen?



Nö, das gibts genau so schon:  --> ArrayList


----------



## JavaForever (16. Jan 2011)

Wieso primfaktiren?
Also als ich dat letztes jahr in der schule hatte(ja, ich bin erst 7.), da haben wir gelernt, dass mans auch so machen kann:

```
int a = 153;
int b = 134;
Int kgv = 0;
If(a < b){
while(kgv % a !=  0){
kgv = kgv * b;
}
}
s.o.p(kgv);
```
bitte sagt mir wenn ich nen denkfehler hatte


----------



## XHelp (16. Jan 2011)

@JavaForever, was soll denn bei dem Code passieren? (selbst wenn man davon absieht, dass die Schleife niemals läuft)


----------



## scandic (16. Jan 2011)

Wenn 

```
kgv = kgv * b;
```
sein soll und eingangs gilt

```
int kgv = 0;
```
dann wird kgv immer 0 sein, weil x *0  = 0.

EDIT:
Es kann  natürlich sein, dass du

```
kgv = kgv + b;
```
meintest (Schreibfehler), dann ginge das wiederum.
Aber ich will ja eigentlich so vorgehen, wie meine Schwester das grad in der 5. Klasse lernt.

Grüße,
scandic


----------



## JavaForever (16. Jan 2011)

oh f**k! Sry
Also da ich keene lust hab den code umzuändern:
Kgv gleich b mal eins
Wenn a teilt kgv dann kgv ermittelt
Sonst
Kgv  gleich b mal zwei
Wenn a teilt kgv dann kgv ermittelt
Sonst
Kgv gleich b mal drei...
U.s.w!


----------



## scandic (16. Jan 2011)

Also solange b addieren bis kgv ein vielfaches von a ist. (Also kgv  % a == 0). Die Methode ist natürlich einfacher zu realisieren.
Danke euch beiden.


----------



## XHelp (16. Jan 2011)

Du kannst kgV mit der Primfaktorzerlegung bestimmt, aber Primfaktorzerlegung mit kgV wohl eher weniger


----------



## JavaForever (16. Jan 2011)

bitteschön


----------



## JohannisderKaeufer (16. Jan 2011)

Brauchst du wirklich eine Primfaktorzerlegung?

Reicht nicht auch schon der Größte gemeinsame Teiler(ggt)?

Für den ggt gibt es einen schönen rekursiven Algorithmus.

Beispiel 
a = 20
b = 28

ggt = 4

a_ = a / ggt = 20 / 4 = 5
b_ = b / ggt = 28 / 4 = 7

kgV = ggt * a_ * b_ = 4 * 5 * 7 = 140


----------



## JavaForever (16. Jan 2011)

@ johannesderkaeufer
ggt != kgv
a_ , b_ , a , b , ggt , kgv sind nicht definiert (ich schließe daraus das soll pseudocode sein...)
ich seh bei dir echt nich mehr durch...


----------



## scandic (16. Jan 2011)

Also ich weiß nicht ob das immer klappt, aber dann müsste ich ja zusätzlich noch den ggT über ne for-Schleife ermitteln. Möglich ist sicherlich vieles, die Frage ist immer nur was wie sinnvoll ist.


----------



## JohannisderKaeufer (16. Jan 2011)

@JavaForever
Das ggt !=kgv ist ist ja wohl selbstverständlich.

Das ist kein Pseudocode das ist ein Rechenweg. vielleicht hätte ich statt ggt = 4, ggt(20,28) = 4 schreiben sollen. 

Wie man auch sieht, sind schleifen nicht nötig.


```
public class KGV{

	public static int ggT(int a, int b){
		if(a==b||b==0) {
			return a;
		}
		else{
			return ggT(b,a%b);
		}
	}
	
	public static int kgv(int a, int b){
		int ggt = ggT(a,b);
		int a_ = a / ggt;
		int b_ = b / ggt;
		return a_ * b_ * ggt;
		
	}

	public static int kgv_alternativ(int a, int b){
		return (a  / ggT(a,b))*b;
	}


	public static void main(String[] args){
		int a = 20;
		int b = 28;
		System.out.println("KGV von "+a+" und " +b+" = "+kgv(a,b));
		
	}
}
```

vergleicht man die Ausführungszeit mit einem iterativen Algorithmus

```
public static long kgv_iterativ(long a, long b){
                long kgv = a;
		while((kgv % b) != 0){
				kgv += a;
		}
		return kgv;
	}
```

so skaliert die Lösung mit der Schleife miserabel, je größer die Zahlen und je kleiner der ggT ist, desto länger wartet man auf sein Ergebnis. Die Lösung die ich aufgezeigt habe, hält sich bei meinen Messungen nahezu konstant bei unter 1 ms.


----------



## JavaForever (16. Jan 2011)

entschuldige wenn ich dir zu nahe getreten bin!
das war keine absicht und nach java-forum agb ja auch nicht erwünscht
mir war nicht klar, dass du das kgv über den ggt berechnen wolltest.
(ich wusste nichma, dass das geht; aber jetzt weiß ichs!  )


----------

