dynamisches Array für Primfaktorzerlegung

scandic

Mitglied
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
 

JavaForever

Mitglied
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:
Java:
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

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

scandic

Mitglied
Wenn
Java:
kgv = kgv * b;
sein soll und eingangs gilt
Java:
int kgv = 0;
dann wird kgv immer 0 sein, weil x *0 = 0.

EDIT:
Es kann natürlich sein, dass du
Java:
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
 
Zuletzt bearbeitet:

JavaForever

Mitglied
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

Mitglied
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.
 
J

JohannisderKaeufer

Gast
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

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

Mitglied
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.
 
J

JohannisderKaeufer

Gast
@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.

Java:
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
Java:
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.
 
Zuletzt bearbeitet von einem Moderator:

JavaForever

Mitglied
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! ;) )
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
kodela Dynamisches Array in einer Klasse Allgemeine Java-Themen 5
P dynamisches Array / Vector Allgemeine Java-Themen 2
N Mehrdimensionales dynamisches Array Allgemeine Java-Themen 3
J Unterschied: Polymorphie und Dynamisches Binden Allgemeine Java-Themen 8
N Eclipse Dynamisches-Web-Project auf anderen Rechner transportieren Allgemeine Java-Themen 5
looparda Dynamisches Konsolenprogramm Allgemeine Java-Themen 3
T Dynamisches p:graphicimage im Datagrid Allgemeine Java-Themen 7
C Dynamisches und sortiertes Auslesen von Properties Allgemeine Java-Themen 2
P Dynamisches Binden Allgemeine Java-Themen 7
X Dynamisches hinzufügen von Panles Allgemeine Java-Themen 4
A Dynamisches Enum? Allgemeine Java-Themen 2
S Dynamisches Manipulieren/Laden von Klassen Allgemeine Java-Themen 4
Z Dynamisches JPanel Allgemeine Java-Themen 10
hdi Dynamisches Instantiieren (Reflections) Allgemeine Java-Themen 4
H2SO3- dynamisches anlegen der dimensionaltität eines arrays Allgemeine Java-Themen 6
reibi Klassenpfad mal anders - dynamisches Laden einer Klasse Allgemeine Java-Themen 7
lumo "Exzessiv" dynamisches generieren Allgemeine Java-Themen 6
R Dynamisches Laden von JNI-Bibliotheken Allgemeine Java-Themen 4
T Dynamisches laden von java Klassen Allgemeine Java-Themen 2
B Dynamisches Linken Allgemeine Java-Themen 15
M Dynamisches ausführen von methoden unbekannter klassen Allgemeine Java-Themen 6
V dynamisches laden von klassen Allgemeine Java-Themen 8
C Dynamisches Nachladen von JARs (Plugin) Allgemeine Java-Themen 3
S Dynamisches Casten Allgemeine Java-Themen 5
M Statisches und dynamisches Binden? Allgemeine Java-Themen 2
S Dynamisches Feld generieren. Allgemeine Java-Themen 10
E Dynamisches Instanziieren Allgemeine Java-Themen 2
B dynamisches Laden aller Klassen in einem Ordner ?? Allgemeine Java-Themen 5
LucasGlockner Effizienter byte-Zugriff auf ein long[]-Array Allgemeine Java-Themen 8
8u3631984 Frage Performance bei Linked List und Array List Allgemeine Java-Themen 5
M Queue mit einem Array implemetieren Allgemeine Java-Themen 16
M Array Rang eines Elements Allgemeine Java-Themen 4
TheSepp Java bestimmtes Array auf den Wert 0 setzen Allgemeine Java-Themen 32
TheSepp Wie kann man Leerzeichen aus einer Array liste entfernen? Allgemeine Java-Themen 10
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
noah1407 Array Allgemeine Java-Themen 3
D Methoden Teil-Array mit Maximalwert bestimmen Allgemeine Java-Themen 23
N einem Array Objekte hinzufügen die ihr Array position gespeichert haben Allgemeine Java-Themen 34
N zweidimensionalen Array in dreidimensionalen Array speichern Allgemeine Java-Themen 4
N Schnellste Methode, ein Array durchzugehen? Allgemeine Java-Themen 9
T Objekt Array Aufgabe mit Busdatenbank Allgemeine Java-Themen 2
L Array und Index Allgemeine Java-Themen 26
L die 3 größten Zahlen im Array Allgemeine Java-Themen 1
G jToggleButton in Array/ArrayList Allgemeine Java-Themen 12
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
Willi.We Array sortieren Allgemeine Java-Themen 5
gotzi242 Array Summe bestimmen tipps? Allgemeine Java-Themen 14
H Matrix ohne Array erstellen Allgemeine Java-Themen 9
Aboya Char Array rekursiv vergleichen Allgemeine Java-Themen 15
V4ll3.Wff Array in Java Allgemeine Java-Themen 4
Noahscript Aus einem byte Array Steuerungszeichen und Code bekommen und ersetzen Allgemeine Java-Themen 3
H Array Sportschütze Allgemeine Java-Themen 6
Sumo_ow "ArrayIndexOutofBoundsException: 2" Array Problem Allgemeine Java-Themen 6
xGh0st2014 Problem mit Java Array Allgemeine Java-Themen 1
M Array verändern Allgemeine Java-Themen 1
A JavaFX 2 dimensionales array Allgemeine Java-Themen 1
LimDul Direktes return eines Array geht nicht Allgemeine Java-Themen 20
S Array dynamisieren oder ArrayList verwenden? Allgemeine Java-Themen 17
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
H Array mit dem Datentype String[] initializieren Allgemeine Java-Themen 7
L ArrayList mit String Arrays in ein Array umwandeln Allgemeine Java-Themen 1
H Elemente aus ArrayList in Array speichern Allgemeine Java-Themen 8
E Datentypen Wie kann ich die Längen der unterschiedlichen Ebenen aus einem Objekt lesen von dem ich weiß, dass es ein mehrdimensionaler Array ist? Allgemeine Java-Themen 3
N Byte Array in Java "dekomprimieren" Allgemeine Java-Themen 3
parrot Array Aufgabe Allgemeine Java-Themen 3
N String Array Eingabe Allgemeine Java-Themen 6
R Warum wird mir in der Konsole das "Standard Array" ausgegeben? Allgemeine Java-Themen 2
N Variablen Array Länge ändern. Allgemeine Java-Themen 8
D Kgv aller Paare aus einem Array mit n integer berechnen Allgemeine Java-Themen 5
W Enumeration ein Array/List als Eigenschaft mitgeben - warum geht das nicht? Allgemeine Java-Themen 0
kodela Problem mit strukturiertem Array Allgemeine Java-Themen 18
A Array Problem Allgemeine Java-Themen 8
Drachenbauer Wie stelle ich fest, ob ein Objekt in meinem Array vorkommt? Allgemeine Java-Themen 5
F Datei in String-Array einlesen Allgemeine Java-Themen 8
L Objekt aus Objekt-array "löschen" Allgemeine Java-Themen 2
I Array Parameter mit 2 Klassen - NullPointerException Allgemeine Java-Themen 3
X Größten Werte in meinem Array löschen? Allgemeine Java-Themen 16
E Angabe wie groß Array sein soll und in for-schleifen diesen Array füllen Allgemeine Java-Themen 3
F 3 Dimensionales Array mit Allgemeine Java-Themen 9
M Steueralgorithmus verwandelt Array in Anfangszustand Allgemeine Java-Themen 9
W Array vs. ArrayList vs. HashMap Allgemeine Java-Themen 20
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
T Objekt in Array packen Allgemeine Java-Themen 6
M Zahlen in Array anordnen Allgemeine Java-Themen 8
M Eclipse Unvollständigen Array ansteuern Allgemeine Java-Themen 2
D Erste Schritte Im Array Werte tauschen Allgemeine Java-Themen 5
Xge For/Array Error: IndexOutOfBounds Allgemeine Java-Themen 4
M Wie kann ich ein int[] Array in einer Methode benutzen? Allgemeine Java-Themen 6
FRI3ND Datentypen Date-Array sortieren - Text mitnehmen? Allgemeine Java-Themen 7
D Integer-Array variabler Größe mit Zahlen befüllen (Schleifen) Allgemeine Java-Themen 0
J Variablen Array ertellen bei model.put Allgemeine Java-Themen 13
S Eindimensionales Array in zweidimensionales Array speichern Allgemeine Java-Themen 5
R convert 2d array list to 2d array Allgemeine Java-Themen 1
J json Array würfel Spalten durcheinander Allgemeine Java-Themen 9
MiMa Array umbau oder Alternative? Allgemeine Java-Themen 5
L Datentypen 3D Array Allgemeine Java-Themen 3
M 2D Array mit unterschiedlichen Längen erstellen und befüllen Allgemeine Java-Themen 11
Mario1409 Methoden JSON Array von URL Allgemeine Java-Themen 8
E Swing Array mit Bildern in GUI darstellen Allgemeine Java-Themen 2
P Array einer abstrakten Klasse Allgemeine Java-Themen 4

Ähnliche Java Themen

Neue Themen


Oben