# Alle Teiler einer Zahl performant berechnen?



## 0001001 (28. Mai 2007)

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 (28. Mai 2007)

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 (28. Mai 2007)

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 (28. Mai 2007)

kleiner_held hat gesagt.:
			
		

> 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 (28. Mai 2007)

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 (28. Mai 2007)

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 (28. Mai 2007)

Leroy42 hat gesagt.:
			
		

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



_n | zahl_ steht in der Mathematik für _n teilt zahl (ohne Rest)_


----------



## Wildcard (28. Mai 2007)

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


----------



## Leroy42 (28. Mai 2007)

Wildcard hat gesagt.:
			
		

> Ü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 (28. Mai 2007)

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


----------

