Alle Teiler einer Zahl performant berechnen?

[0001001]

Hallo Ihr,

wie berechne ich alle Teiler einer Zahl performant?
Die simple Methode ist klar:

	public static void primefactor(int zahl){
		int zahlhalbe = zahl/2; // es reicht bis zahl/2 zu pruefen
		for(int i=1;i<=zahlhalbe;i++){
			if(zahl%i==0){
				System.out.print(i+" ");
			}
	    } 
	}

Allerdings ist diese bei größeren Zahlen absolut inperformant. Ich will keinen perfekten Algorithmus alà quadratisches Sieb o.ä. implementieren, aber etwas verbessern müsste man den Algorithmus doch können. Leider fällt mir im Moment nichts ein.
Habt ihr eine Idee?

 

[kleiner_held]

Primfaktorzerlegung ist halt rechenaufwändig.
Wenn dir das quadratische Sieb zu komplex ist, dann schau doch mal ob hier ein Algorithmus dabei ist der dir zusagt.

Wobei es mich nicht überraschen würde, wenn sich mittels Suchmaschine eine Java-Implementierung des Algorithmus quadratisches Sieb finden ließe.

 

[Leroy42]

Als erstes fällt mir mal ein, wenn du auf die Reihenfolge
keinen Wert legst, oder die Zahlen vor der Ausgabe in
eine List speicherst, nur bis zur Quadratwurzel zu testen
und auch immer den Gegenpart auszugeben

n | zahl ==> (zahl/n) | zahl

Edit: Damit O(n) ---> O(sqrt(n))

 

[Leroy42]

Primfaktorzerlegung ist halt rechenaufwändig.

Wäre auch nicht genau das, was 000101010 sucht, obwohl man
natürlich über die Primfaktorzerlegung

n = p1^n1 * p2^n2 * ...

auch relativ einfach alle Teiler bestimmen kann.

 

[0001001]

hm,
das quadratische Sieb ist mir in der Tat zu kompliziert. Zumindest für das simple Programm, für das ich die Teiler benötige.

Nur bis zur Wurzel zu rechnen reicht nicht aus, da ich ja alle Teiler der Zahl brauche.
Beispiel:
Teiler von 16: 1,2,4,8
Würde ich nur bis zur Wurzel rechnen, würde nur 1,2,4 ausgegeben werden.

 

[Leroy42]

Hast du meine Erklärung mit dem Gegenpart überlesen? :shock:

Beispiel 16:

sqrt(16) = 4

1 und 16/1 = 16
2 und 16/2 = 8
4

Also Teiler von 16: 1,2,4,8,16

 

[Leroy42]

n | zahl ==> (zahl/n) | zahl

n | zahl steht in der Mathematik für n teilt zahl (ohne Rest)

 

[Wildcard]

Übrigens ganz schlecht wenn der Name einer Methode (primefactor) im Krassen Gegensatz zu ihrer Funktion (alle Teiler) steht.

 

[Leroy42]

Übrigens ganz schlecht wenn der Name einer Methode (primefactor) im Krassen Gegensatz zu ihrer Funktion (alle Teiler) steht.

:shock: Stimmt ja, hab ich gar nicht gelesen!
Dann ist ja kleinerHeld's Mißverständnis begreifbar.

Also @ 001001: Geh' in die Ecke und schäm dich! :noe:

 

[kleiner_held]

Jepp - ich hab mich vom Methodennamen verwirren lassen. Obwohl Threadtitel und Fragestellung schon eindeutig waren, also ganz rausreden kann ich mich auch nicht