Teilermenge ermitteln

[Nicolai1234]

Hallo,
in meinem aktuellen Projekt benötge ich die Teilermengen von Zahlen.
Also z. B. T9={1,3,9}

Klar kann ich diese mit einer Schleife errechnen; das finde ich aber nicht so schön bzw. Schleifen dauern bei großen Zahlen einfach zu lang...
Ich habe schon gesucht, aber nichts gefunden:
Gibt es ein rechnerisches Verfahren, um die Teilermengen bzw. deren Anzahl zu berechen?

Besonders die Anzahl ist mir wichtig.

Vielen Dank im voraus

[Phistev]

Bisher gibt es keine besseren Verfahren, ansonsten könnte RSA u. ä. einpacken, da die darauf basieren, dass man eine Zahl nur per Brute-Force faktorisieren (in die Teiler zerlegen) kann. Nützlich könnten hier Lookup-Tables oder Primfaktorzerlegung sein (dazu denk ich mir noch was aus).

[Nicolai1234]

Ich habe heute nochmal meinen Mathelehrer gefragt und er redete auch etwas über Primfaktorzerlegung.
Genaueres konnte er mir aber auch nicht sagen...

[Phistev]

Bei der PFZ zerlegt man eine Zahl in die Primfaktoren. Am Ende steht dann in etwa 12=2*2*3. Die Teiler der Zahl sind die Primzahlen selber und alle Produkte aus den Primzahlen. Die Produkte per Function auszurechnen, das ist das Interessante (Frage am Rande: Wie erhalte ich das erste Element eines Arrays, welches dann auch entfernt wird?)... Vorteil (oder auch nicht) der PFZ gegenüber der direkten Bestimmung der Teiler: Laufzeit sqrt(n)+Produktbildung gegen n/2

[Eichhoernchen]

wie wäre es mit Rekursion, so haben wir das in der Schule gemacht!

[BlackJack]

Zitat von Eichhoernchen:

wie wäre es mit Rekursion, so haben wir das in der Schule gemacht!

naja, sagen wir so, jedes Iterativ lösbare Problem lässt sich auch rekursiv lösen, von daher: Ja.

[CLRS530]

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

[alzaimar]

Zitat von CLRS530:

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

Bitte zu letzter Aussage ein Beispiel.

[jfheins]

@CLRS530:

Delphi-Quellcode:

for i := 1 to 5 do
  maches (i);

=

Delphi-Quellcode:

procedure recurse (i: integer)
begin
  maches (i);
  if i < 5 then
    recurse (i + 1);
end;

recurse (1)

[BlackJack]

Zitat von CLRS530:

Das ist schonmal total falsch, du kannst jede rekursive Lösung iterativ machen (teilweise ziemlich umständlich, z. B. beim durchgehen der Ordner auf der Festplatte oder alle Wurzeln eines Trees).

Aber iterative Lösungen kannst du absolut nicht alle zu einer rekursiven machen.

Dann zeig mir bitte mal eine rein Iterative Variante der Ackermann-Funktion, das sollte deiner Meinung nach ja auf jeden Fall möglich sein.

Und wenn du schon dabei bist, dann zeig mir auch bitte eine Iterative Funktion, die sich nicht in eine Rekursion umwandeln lässt.