Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Teiler einer Zahl finden
Autor
Schule Teiler einer Zahl finden
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Themenstart: 2021-10-16

Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. Jetzt hab ich was in php geschrieben, was aber verwurkst ist und so auf dem Zettel gehts auch nicht recht flüssig...;) Es ist besonders "schwierig" bei solchen highly composite numbers. Löst man das mit 4 geschachtelten For Loops? Ist die Zahl abundant, deficient, "normal" usw.? Das kann ich dann aus der Summe der Teiler eruieren..


   Profil
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 470
Wohnort: Deutschland
  Beitrag No.1, eingetragen 2021-10-16

Hallo juergenX, reicht es nicht, wenn du alle Kombinationen der Teiler bildest und diese dann ausrechnest? Die Primfaktoren sind ja bereits gegeben. 2 2 2 2 3 2 5 2 7 2 2 2 2 2 3 2 2 5 2 2 7 usw. Dann rechnest du alles aus


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.2, vom Themenstarter, eingetragen 2021-10-16

\quoteon(2021-10-16 00:01 - juergenX im Themenstart) Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. \quoteoff Ausgeschrieben ist das 2*2*2*3*3*5*7*7 Also kombinatorisch gesehen muss man ja erstens alle einzelnen verschiedenen Ziffern nehmen 2,3,5,7 dann alle Dupel 2,3 2,2 2.5 2.7 tripel 2,3,5 2,2,2 3,3,5 quadrupel 2,2,3,7 2,3,7,7 usw. die Höchtse ist wohl 7*7*5*3*3*2*2 = 8820 Die Kleinste 1 = 2^0. Wieviel sind das ? ich wollte das in ein simples Programm giessen, ist wohl schon spät die N8 gg


   Profil
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 470
Wohnort: Deutschland
  Beitrag No.3, eingetragen 2021-10-16

Hallo, falls es dich interessiert: \sourceon JavaScript const arr = [2, 2, 2, 3, 3, 5, 7, 7] console.log(arr.reduce((prev, cur) => prev * cur, 1)) const dividers = [[1]] const composeDivider = (index, value, numbers) => { if (index >= arr.length) return const newValue = arr[index] if (value != null && newValue === arr[index - 1]) { return composeDivider(index + 1, newValue, numbers) } if (value !== newValue) { dividers.push([...numbers, newValue]) } composeDivider(index + 1, newValue, numbers) composeDivider(index + 1, null, [...numbers, arr[index]]) } composeDivider(0, null, []) console.log(dividers) dividers.splice(dividers.length - 1, 1) console.log(dividers .map(arr => arr.reduce((prev, cur) => prev * cur, 1)) .sort((a, b) => a < b ? -1 : 1)) \sourceoff Ausgabe: \sourceon JavaScript [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 40, 42, 45, 49, 56, 60, 63, 70, 72, 84, 90, 98, 105, 120, 126, 140, 147, 168, 180, 196, 210, 245, 252, 280, 294, 315, 360, 392, 420, 441, 490, 504, 588, 630, 735, 840, 882, 980, 1176, 1260, 1470, 1764, 1960, 2205, 2520, 2940, 3528, 4410, 5880, 8820] \sourceoff Ich gestehe, dass die if-Bedingungen etwas komplizierter waren. Wenn einem die Performance egal ist, dann kommt man auch viel einfacher ans Ziel. Es sollten 71 sein.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7299
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2021-10-16

\quoteon(2021-10-16 01:29 - Scynja in Beitrag No. 3) Es sollten 71 sein. \quoteoff Das ist richtig. Für die 2er-Potenzen eines Teilers gibt es 4 Möglichkeiten (\(2^0,2^1,2^2,2^3\)) Für die 3er-Potenzen eines Teilers gibt es 3 Möglichkeiten Für die 5er-Potenzen eines Teilers gibt es 2 Möglichkeiten Für die 7er-Potenzen eines Teilers gibt es 3 Möglichkeiten Zusammen: 4*3*2*3 = 72. Davon muss noch 1 abgezogen werden, da die Zahl selbst nicht mitgezählt werden soll. Oder als Programm: \sourceon nameDerSprache Für t = 1 bis 17640-1 Wenn (17640-1)/t ganzzahlig drucke(t) \sourceoff


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2184
  Beitrag No.5, eingetragen 2021-10-16

Huhu, siehe auch: https://de.wikipedia.org/wiki/Teileranzahlfunktion Gruß, Küstenkind


   Profil
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 470
Wohnort: Deutschland
  Beitrag No.6, eingetragen 2021-10-16

\quoteon(2021-10-16 10:47 - StrgAltEntf in Beitrag No. 4) \quoteon(2021-10-16 01:29 - Scynja in Beitrag No. 3) Es sollten 71 sein. \quoteoff Das ist richtig. Für die 2er-Potenzen eines Teilers gibt es 4 Möglichkeiten (\(2^0,2^1,2^2,2^3\)) Für die 3er-Potenzen eines Teilers gibt es 3 Möglichkeiten Für die 5er-Potenzen eines Teilers gibt es 2 Möglichkeiten Für die 7er-Potenzen eines Teilers gibt es 3 Möglichkeiten Zusammen: 4*3*2*3 = 72. Davon muss noch 1 abgezogen werden, da die Zahl selbst nicht mitgezählt werden soll. Oder als Programm: \sourceon nameDerSprache Für t = 1 bis 17640-1 Wenn (17640-1)/t ganzzahlig drucke(t) \sourceoff \quoteoff Richtig. Das Problem stößt aber schnell an seine Grenzen, wenn wir z. B. 98377^2 * 98387^3 * 98389^5 * 98407^7 als Zahl haben, dürfte das Programm einige Zeit brauchen, um zu terminieren. (wobei man hier auch noch das Problem des erweiterten Zahlenraums betrachten muss).


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.7, eingetragen 2021-10-16

\quoteon(2021-10-16 00:01 - juergenX im Themenstart) Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. \quoteoff Die Prozedur function factors(x : ℕ, y : ℕ) : list[ℕ] <= if y = 0 then 1 :: ø else if y = 1 then 1 :: ø else if x > y then if y | x then y :: factors(x, y-1) else factors(x, y-1) end_if else factors(x, y-1) end_if end_if end_if löst das Problem, denn es gilt ∀ n, x : ℕ x ≠ 0 ∧ n ∈ factors(x, x-1) → n ∣ x % factors(x, x-1) enthält nur Teiler von x % ∀ n, x : ℕ n ≠ 0 ∧ x > n ∧ n ∣ x → n ∈ factors(x, x-1) % factors(x, x-1) enthält alle Teiler ungleich x von x % PS: ø bezeichnet die leere Liste und n :: k entsteht aus der Liste k indem n vorangestellt wird.


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.8, vom Themenstarter, eingetragen 2021-10-16

\quoteon(2021-10-16 13:48 - Zwerg_Allwissend in Beitrag No. 7) \quoteon(2021-10-16 00:01 - juergenX im Themenstart) Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. \quoteoff \quoteoff Danke for die zahlreichen Tips Anzahl 71 ist klar, \sourceon nameDerSprache function factors(x : ℕ, y : ℕ) : list[ℕ] <= if y = 0 then 1 :: ø else if y = 1 then 1 :: ø else if x > y then if y | x then y :: factors(x, y-1) else factors(x, y-1) end_if else factors(x, y-1) end_if end_if end_if \sourceoff Darf ich hier nachhaken: ich verstehe nicht factors(x, y-1) was ist x und y und welche Sprache ist das? Zu der javascript funktion \sourceon javascript const arr = [2, 2, 2, 3, 3, 5, 7, 7] console.log(arr.reduce((prev, cur) => prev * cur, 1)) const dividers = [[1]] const composeDivider = (index, value, numbers) => { if (index >= arr.length) return const newValue = arr[index] if (value != null && newValue === arr[index - 1]) { return composeDivider(index + 1, newValue, numbers) } if (value !== newValue) { dividers.push([...numbers, newValue]) } composeDivider(index + 1, newValue, numbers) composeDivider(index + 1, null, [...numbers, arr[index]]) } composeDivider(0, null, []) console.log(dividers) dividers.splice(dividers.length - 1, 1) console.log(dividers .map(arr => arr.reduce((prev, cur) => prev * cur, 1)) .sort((a, b) => a < b ? -1 : 1)) \sourceoff möchte ich gern wissen, wie mam die implementiert innerhalb einer Html datei? Danke


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.9, eingetragen 2021-10-16

Hier eine kleine Pythonvariante. Sollte sich problemlos 1:1 übersetzen lassen. Man kann es natürlich auch rekursiv implementieren. \sourceon Python \numberson # faktorisierung: [(prim_faktor,exponent)] def teiler(faktorisierung): teiler_liste = [] stack = [(1,0)] while stack: prod,idx = stack[-1] stack.pop() if idx == len(faktorisierung): teiler_liste.append(prod) continue prim,Exp = faktorisierung[idx] for e in range(Exp+1): stack.append((prod*prim**e,idx+1)) return sorted(teiler_liste) T = teiler([(2,3),(3,2),(5,1),(7,2)]) print(f"Es wurden {len(T)} Teiler erzeugt!") print(T) \sourceoff


   Profil
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 470
Wohnort: Deutschland
  Beitrag No.10, eingetragen 2021-10-16

Es gibt x Möglichkeiten: z. B. inline: https://www.codespeedy.com/how-to-write-inline-javascript-code-in-html/ Zum Ausprobieren reicht es auch in gängigen Browsern F12 zu drücken und im Consolen-Reiter den Code reinzukopieren.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.11, eingetragen 2021-10-17

Obiges Programm Quick&Dirty übersetzt in Inline-Javascript: \sourceon html \numberson Teilerberechnung

Teiler von 2^3 * 3^2 * 5 * 7^2

Teiler von 2^64

\sourceoff



   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.12, eingetragen 2021-10-17

\quoteon(2021-10-16 17:58 - juergenX in Beitrag No. 8) \quoteon(2021-10-16 13:48 - Zwerg_Allwissend in Beitrag No. 7) \quoteon(2021-10-16 00:01 - juergenX im Themenstart) Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. \quoteoff \quoteoff \sourceon nameDerSprache function factors(x : ℕ, y : ℕ) : list[ℕ] <= if y = 0 then 1 :: ø else if y = 1 then 1 :: ø else if x > y then if y | x then y :: factors(x, y-1) else factors(x, y-1) end_if else factors(x, y-1) end_if end_if end_if \sourceoff Darf ich hier nachhaken: ich verstehe nicht factors(x, y-1) was ist x und y und welche Sprache ist das? \quoteoff 'factors' ist eine rekursive Prozedur mit formalen Parametern x und y. Der Parameter y wird solange heruntergezählt [=> rekursiver Aufruf factors(x, y-1)] bis y = 1 gilt. Mit factors(x, x-1) erhält man die Liste aller Teiler. Beispiel: factors(12, 11) => factors(12, 10) % denn 11 teilt nicht 12 % => factors(12, 9) % denn 10 teilt nicht 12 % => factors(12, 8) % denn 9 teilt nicht 12 % => factors(12, 7) % denn 8 teilt nicht 12 % => factors(12, 6) % denn 7 teilt nicht 12 % => 6 :: factors(12, 5) % denn 6 teilt 12 % => 6 :: factors(12, 4) % denn 5 teilt nicht 12 % => 6 :: 4 :: factors(12, 3) % denn 4 teilt 12 % => 6 :: 4 :: 3 :: factors(12, 2) % denn 3 teilt 12 % => 6 :: 4 :: 3 :: 2 :: factors(12, 1) % denn 2 teilt 12 % => 6 :: 4 :: 3 :: 2 :: 1 :: ø % denn 1 teilt 12 % d.h. 6, 4, 3, 2, 1 sind die gesuchten Teiler von 12. Man spart sich so die Primfaktorzerlegung. 'factors' kann auch mit einer while-Schleife programmiert werden. Ist die Primfaktorzerlegung jedoch aus irgendeinem Grund bereits gegeben, so wird es noch einfacher. Um die Teiler von 'n' zu bestimmen geht man wie folgt vor: (1) ℙf(n) := Liste aller Primfaktoren von n (wenn n ≥ 2) (2) ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n) (3) P(℘ℓ(ℙf(n))) := die Menge aller Produkte der Elemente der Listen in ℘ℓ(ℙf(n)) P(℘ℓ(ℙf(n))) ist dann die Menge aller Teiler von n (inklusive n). Beispiel: (1) ℙf(12) := <2, 2, 3> (2) ℘ℓ(ℙf(12)) := <ø, <2>, <2>, <3>, <2, 2>, <2, 3>, <2, 3>, <2, 2, 3>> (3) P(℘ℓ(ℙf(n))) := {1, 2, 3, 4, 6, 12}


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.13, eingetragen 2021-10-17

\quoteon(2021-10-17 10:24 - Zwerg_Allwissend in Beitrag No. 12) Man spart sich so die Primfaktorzerlegung. 'factors' kann auch mit einer while-Schleife programmiert werden. Ist die Primfaktorzerlegung jedoch aus irgendeinem Grund bereits gegeben, so wird es noch einfacher. Um die Teiler von 'n' zu bestimmen geht man wie folgt vor: (1) ℙf(n) := Liste aller Primfaktoren von n (wenn n ≥ 2) (2) ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n) (3) P(℘ℓ(ℙf(n))) := die Menge aller Produkte der Elemente der Listen in ℘ℓ(ℙf(n)) P(℘ℓ(ℙf(n))) ist dann die Menge aller Teiler von n (inklusive n). Beispiel: (1) ℙf(12) := <2, 2, 3> (2) ℘ℓ(ℙf(12)) := <ø, <2>, <2>, <3>, <2, 2>, <2, 3>, <2, 3>, <2, 2, 3>> (3) P(℘ℓ(ℙf(n))) := {1, 2, 3, 4, 6, 12} \quoteoff Beide Algorithmen wirken auf mich nicht besonders effizient oder missverstehe ich da etwas?


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.14, eingetragen 2021-10-17

\quoteon(2021-10-17 10:49 - DerEinfaeltige in Beitrag No. 13) \quoteon(2021-10-17 10:24 - Zwerg_Allwissend in Beitrag No. 12) Beide Algorithmen wirken auf mich nicht besonders effizient oder missverstehe ich da etwas? \quoteoff \quoteoff Um alle Teiler von n mittels 'factors' zu finden sind n Schritte erforderlich, der Aufwand von 'factors(n, n-1)' ist also linear in n. 'factors' implementiert also eine einfache naive Suche. Verwendet man die Primfaktorzerlegung so hat man deren Aufwand. So weit ich weiß wächst der Aufwand zur Berechnung von ℙf(n) exponentiell mit der Größe von n (da bin ich aber nicht sattelfest). Dazu kommt der exponentielle Aufwand 2^|ℙf(n)| zur Berechnung von ℘ℓ(ℙf(n)). Zusätzlich noch der Aufwand 2^|ℙf(n)| zur Berechnung von P(℘ℓ(ℙf(12))). Ob das jetzt effizient oder ineffizient ist weiß ich nicht. Dazu müßte man wissen, ob es Algorithmen mit geringeren Aufwand gibt. Kennst Du welche?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.15, eingetragen 2021-10-17

\quoteon(2021-10-17 13:26 - Zwerg_Allwissend in Beitrag No. 14) Ob das jetzt effizient oder ineffizient ist weiß ich nicht. Dazu müßte man wissen, ob es Algorithmen mit geringeren Aufwand gibt. Kennst Du welche? \quoteoff Ich habe meine Pythonversion mal getestet: Für relativ große Zahlen (Tausende Stellen) wird die Arithmetik zum Flaschenhals. Für kleinere Zahlen ist mein Algorithmus annäherend linear in der Anzahl der Teiler. \sourceon Python \numberson from time import time_ns for T in [ [(2,40000)], [(2,1000),(3,1000)], [(2,35),(3,35),(5,35),(7,35)], [(2,5),(3,5),(5,5),(7,5),(11,5),(13,5),(17,5),(19,5)], [(2,1),(3,1),(5,1),(7,1),(11,1),(13,1),(17,1),(19,1),(23,1),(29,1), (31,1),(37,1),(41,1),(43,1),(47,1),(53,1),(59,1),(61,1),(67,1),(71,1)]]: t0 = time_ns() teiler_liste = teiler(T) t1 = time_ns() print(f"{len(teiler_liste)} Teiler (max = 10^{len(str(teiler_liste[-1]))}) berechnet in {(t1-t0)/1e6:.1f}ms.") 40001 Teiler (max = 10^12042) berechnet in 2449.6ms. 1002001 Teiler (max = 10^779) berechnet in 2831.3ms. 1679616 Teiler (max = 10^82) berechnet in 2484.5ms. 1679616 Teiler (max = 10^35) berechnet in 2807.5ms. 1048576 Teiler (max = 10^27) berechnet in 2227.8ms. \sourceoff


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.16, eingetragen 2021-10-17

\quoteon(2021-10-17 15:24 - DerEinfaeltige in Beitrag No. 15) \quoteon(2021-10-17 13:26 - Zwerg_Allwissend in Beitrag No. 14) Ob das jetzt effizient oder ineffizient ist weiß ich nicht. Dazu müßte man wissen, ob es Algorithmen mit geringeren Aufwand gibt. Kennst Du welche? \quoteoff Ich habe meine Pythonversion mal getestet: Für relativ große Zahlen (Tausende Stellen) wird die Arithmetik zum Flaschenhals. \quoteoff Das läßt exponentiellen Aufwand vermuten. \quoteon Für kleinere Zahlen ist mein Algorithmus annäherend linear in der Anzahl der Teiler. \quoteoff Ja, am Anfang ist das Wachstum gering, aber dann geht die Post ab. Das haben wir ja bei den Inzidenzen der Pandemie schon gesehen. Kannst Du mal kurz sagen, wie Dein Algorithmus funktioniert. So wie ich das verstanden habe werden zunächst die Primfaktoren berechnet, richtig? Wie bekommt man jetzt die Teiler? Hier die imperative Fassung meines Algorithmus: program factors(x : ℕ) var y : ℕ var r : list[ℕ] if x = 0 then r := ø else if x = 1 then r := 1 :: ø else r := ø y := x / 2 while y > 1 do if y | x then r := y :: r end_if y := y - 1 end_while r := 1 :: r end_if end_if return(r) end_program Dabei ist / die nach unten gerundete Division. Das ist ja schnell programmiert, und Du könntest das mit den Werten Deines Algorithmus vergleichen - würde mich interessieren. Meine Vermutung, 'factors' ist schneller, da linear bzgl. der Eingabe.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.17, eingetragen 2021-10-17

\quoteon(2021-10-17 19:27 - Zwerg_Allwissend in Beitrag No. 16) program factors(x : ℕ) var y : ℕ var r : list[ℕ] if x = 0 then r := ø else if x = 1 then r := 1 :: ø else r := ø y := x / 2 while y > 1 do if y | x then r := y :: r end_if y := y - 1 end_while r := 1 :: r end_if end_if return(r) end_program Dabei ist / die nach unten gerundete Division. Das ist ja schnell programmiert, und Du könntest das mit den Werten Deines Algorithmus vergleichen - würde mich interessieren. Meine Vermutung, 'factors' ist schneller, da linear bzgl. der Eingabe. \quoteoff Ich verstehe deine Funktion nicht. Schon die Parameter passen ja nicht zum Problem. Gesucht ist eine Funktion list[(N,N)] -> list[N] die zu einer vorgegebenen Primfaktorzerlegung die Teilermenge berechnet. Falls ich deinen Code verstehe, nimmt dieser die komplette Zahl (man berechnet also zunächst das Produkt) und berechnet dann die Teilermenge per Brute-Force durch Probedivision. So ein Algorithmus würde allerdings bereits für die Berechnung der Teilerliste vom Produkt der ersten 20 Primzahlen länger benötigen als das geschätzte Alter des Universums, geschweige denn wie lange er zum Berechnen der 40001 Teiler von $2^{40000}$ benötigen würde. Mein Algorithmus bildet alle Potenzen eines Primfaktors und multipliziert diese mit allen Produkten der restlichen Primfaktoren. Die Anzahl Iterationen ist daher linear in der Anzahl der Teiler und der unterschiedlichen Primfaktoren. Für größere Zahlen kommt noch die Laufzeit der Multiplikationsroutine zur Geltung.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.18, eingetragen 2021-10-18

Ich habe noch einmal verglichen, was passiert, wenn man die Faktorisierung nicht kennt: \sourceon Python \numberson from time import time_ns # Naive Prime Sievle def sievle(N): L = [1 for i in range(N+1)] p = 2 while p*p <= N: for t in range(p*p,N+1,p): L[t] = 0 p += 1 while L[p] == 0: p += 1 return [p for p in range(2,N+1) if L[p]] # Find all Divisors of N using Test Division # for all Natural Numbers up to sqrt(N) def test_division(N): Div = [] d = 1 while d*d <= N: if N % d == 0: Div.append(d) _d = N // d if _d != d: Div.append(_d) d += 1 Div.sort() return Div # Factorize N with the Help of a # precomputed List of Primes def factorize(N,prime_list): Fac = [] n = N for p in prime_list: if p*p > N: if n > 1: Fac.append((n,1)) break if n % p == 0: e = 0 while n % p == 0: n //= p e += 1 Fac.append((p,e)) return Fac # Calculate all Divisors of a Number given its # Factorization as a List of Tuples (prime, exponent) def create_divisor_list(factorization): Div = [] stack = [(1,0)] while stack: prod,idx = stack[-1] stack.pop() if idx == len(factorization): Div.append(prod) continue prim,Exp = factorization[idx] for e in range(Exp+1): stack.append((prod*prim**e,idx+1)) Div.sort() return Div # Precompute the Prime List using a Sievle t0 = time_ns() prime_list = sievle(4000000) print(f"Sieving Primes took {(time_ns()-t0)/1e6:.1f}ms") # Factorize the Number N and create the List of Divisors using the Factorization def divisor_list(N): global prime_list return create_divisor_list(factorize(N,prime_list)) # Find all Divisors of Numbers in Iterable numbers # and return the time in ms and the sum of all Divisors as Checksum def time_function(function,numbers): t0 = time_ns() S = 0 for n in numbers: S += sum(function(n)) return (time_ns() - t0)/1e6, S # Test both Algorithms using Numbers in # Range [10^E; 10^E + 100) for E in range(3,14): for func in [test_division,divisor_list]: T,S = time_function(func,range(10**E,10**E+100)) print(f"10^{E:02d}: {func.__name__.ljust(14)} took {T:9.1f}ms; Checksum {S:18d}") Ausgabe: Sieving Primes took 938.3ms 10^03: test_division took 1.0ms; Checksum 172549 10^03: divisor_list took 2.0ms; Checksum 172549 10^04: test_division took 3.0ms; Checksum 1652704 10^04: divisor_list took 4.0ms; Checksum 1652704 10^05: test_division took 9.0ms; Checksum 16444818 10^05: divisor_list took 7.0ms; Checksum 16444818 10^06: test_division took 23.0ms; Checksum 164283553 10^06: divisor_list took 10.0ms; Checksum 164283553 10^07: test_division took 73.5ms; Checksum 1645954094 10^07: divisor_list took 10.0ms; Checksum 1645954094 10^08: test_division took 168.0ms; Checksum 16465845269 10^08: divisor_list took 17.0ms; Checksum 16465845269 10^09: test_division took 417.8ms; Checksum 164923742984 10^09: divisor_list took 43.0ms; Checksum 164923742984 10^10: test_division took 1668.7ms; Checksum 1643314750071 10^10: divisor_list took 135.0ms; Checksum 1643314750071 10^11: test_division took 5358.8ms; Checksum 16412699078504 10^11: divisor_list took 304.0ms; Checksum 16412699078504 10^12: test_division took 16762.5ms; Checksum 164212160037675 10^12: divisor_list took 952.1ms; Checksum 164212160037675 10^13: test_division took 53663.8ms; Checksum 1643415993251654 10^13: divisor_list took 2649.1ms; Checksum 1643415993251654 \sourceoff


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.19, vom Themenstarter, eingetragen 2021-10-18

Mir liegen die PFZ als Feld in PHP bis 250000 in der folgenden Form vor: \sourceon php $allFactors = array ( 2 => array ( 'rad' => 2, 2 => 1, ), . . 107 => array ( 'rad' => 107, 107 => 1, ), 108 => array ( 'rad' => 6, 2 => 2, 3 => 3, ), 109 => array ( 'rad' => 109, 109 => 1, ), 110 => array ( 'rad' => 110, 2 => 1, 5 => 1, 11 => 1, ), 111 => array ( 'rad' => 111, 3 => 1, 37 => 1, ), 112 => array ( 'rad' => 14, 2 => 4, 7 => 1, ), \sourceoff Mit rad ist das Radikal der Zahl gemeint. Es ergibts sich eine "recht einfache" Loesung \sourceon php define ("newl","\n
"); function GetDivisors($factorsA,$number) { $bases = array(); $exponents = array(); foreach ($factorsA as $key =>$value) { if (is_int($key)) { $bases[] = $key; $exponents[]=$value; } } echo newl."bases of : " .$number." sind : "; foreach ($bases as $value) echo $value." ,"; echo newl." highest exponents of number : ".$number." sind : "; foreach ($exponents as $value) echo $value." , "; $divisors = array(); $uniques= array(); Foreach ($bases as $key=>$value) { echo newl." basis : ".$value; echo " higest exponent for ".$value." is ". $exponents[$key]; for ($loop = 0; $loop <= $exponents[$key] ;$loop ++) { $newdivisor = pow($value,$loop); //echo newl." loop =".$loop." newdivisor = ".$newdivisor; $divisors[] = $newdivisor; } } echo newl."alle Teiler von ".$number." sind :"; sort($divisors); $uniques = array_unique($divisors); foreach ($uniques as $value) echo " | ".$value; echo newl."end of GetDivisors".newl; } \sourceoff Ouput fuer 112 bases of : 112 sind : 2 ,7 , highest exponents of number : 112 sind : 4 , 1 , basis : 2 higest exponent for 2 is 4 basis : 7 higest exponent for 7 is 1 alle Teiler von 112 sind : | 1 | 2 | 4 | 7 | 8 | 16 end of GetDivisors Man kann jetzt noch sum of divisors s(n), number of divisors d(n), etc. einfuegen und so ein komplexes assoziatives array bekommen. Edit ich sehe gerad da fehlt der letzte hier 56 ich schau das nochmal an... Nochmal Danke fuer die vielen Versionen. Bei der html Version Danke dafuer! koennte man noch nette Farben und Tabellen einfuegen... In meiner ist noch n Fehler der verschachtelten For Loops 😴



   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.20, vom Themenstarter, eingetragen 2021-10-19

\quoteon(2021-10-17 10:24 - Zwerg_Allwissend in Beitrag No. 12) \quoteon(2021-10-16 17:58 - juergenX in Beitrag No. 8) \quoteon(2021-10-16 13:48 - Zwerg_Allwissend in Beitrag No. 7) \quoteon(2021-10-16 00:01 - juergenX im Themenstart) Moin habe eien scheinbar simples Programmierproblem: Finde alle Teiler einer Zahl, die mir vorliegt in der Form $\displaystyle 2^3*3^2*5*7^2 = 17640$ Finde alle Teiler incl. 1 ohne die Zahl selbst.. \quoteoff \quoteoff \sourceon nameDerSprache function factors(x : ℕ, y : ℕ) : list[ℕ] <= if y = 0 then 1 :: ø else if y = 1 then 1 :: ø else if x > y then if y | x then y :: factors(x, y-1) else factors(x, y-1) end_if else factors(x, y-1) end_if end_if end_if \sourceoff Darf ich hier nachhaken: ich verstehe nicht factors(x, y-1) was ist x und y und welche Sprache ist das? \quoteoff (1) ℙf(n) := Liste aller Primfaktoren von n (wenn n ≥ 2) (2) ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n) (3) P(℘ℓ(ℙf(n))) := die Menge aller Produkte der Elemente der Listen in ℘ℓ(ℙf(n)) P(℘ℓ(ℙf(n))) ist dann die Menge aller Teiler von n (inklusive n). Beispiel: (1) ℙf(12) := <2, 2, 3> (2) ℘ℓ(ℙf(12)) := <ø, <2>, <2>, <3>, <2, 2>, <2, 3>, <2, 3>, <2, 2, 3>> (3) P(℘ℓ(ℙf(n))) := {1, 2, 3, 4, 6, 12} \quoteoff Ja Gerade das letzte Erstellen der Teillisten ist am aufwendigste, und man vertut sich im programmieren,wie in meinem Prog. Ich werde das noch überarbeiten. Man muss inn 3*3*2*2*2**5*7*7 eben alle Teillisten herausfiltetn , was ja auch in einigen eurer Programme realisiert ist... Wir wissen (wiki), dass d(n) =(e1+1)(e2+1)(e3+1)(e4+1) ist also hier 3*4*2*3=72.


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.21, eingetragen 2021-10-19

\quoteon (1) ℙf(n) := Liste aller Primfaktoren von n (wenn n ≥ 2) (2) ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n) (3) P(℘ℓ(ℙf(n))) := die Menge aller Produkte der Elemente der Listen in ℘ℓ(ℙf(n)) P(℘ℓ(ℙf(n))) ist dann die Menge aller Teiler von n (inklusive n). Beispiel: (1) ℙf(12) := <2, 2, 3> (2) ℘ℓ(ℙf(12)) := <ø, <2>, <2>, <3>, <2, 2>, <2, 3>, <2, 3>, <2, 2, 3>> (3) P(℘ℓ(ℙf(n))) := {1, 2, 3, 4, 6, 12} \quoteoff \quoteon Ja Gerade das letzte Erstellen der Teillisten ist am aufwendigste, \quoteoff Für wen - für den Programmierer oder für den Computer? 😃 \quoteon ... und man vertut sich im programmieren,wie in meinem Prog. Ich werde das noch überarbeiten. \quoteoff Ich verwende function [infix*,50] ⊕(i : @ITEM, K : list[list[@ITEM]]) : list[list[@ITEM]] <= if ?ø(K) then ø else (i :: hd(K)) :: (i ⊕ tl(K)) end_if function ℘ℓ(k : list[@ITEM]) : list[list[@ITEM]] <= if ?ø(k) then ø else if ?ø(tl(k)) then (hd(k) :: ø) :: ø else (hd(k) :: ø) :: (℘ℓ(tl(k)) <> hd(k) ⊕ ℘ℓ(tl(k))) end_if end_if und erhalte zum Beispiel ➩ ℘ℓ(1 :: 2 :: 3 :: 4 :: ø) ➲ (1 :: ø) :: (2 :: ø) :: (3 :: ø) :: (4 :: ø) :: (3 :: 4 :: ø) :: (2 :: 3 :: ø) :: (2 :: 4 :: ø) :: (2 :: 3 :: 4 :: ø) :: (1 :: 2 :: ø) :: (1 :: 3 :: ø) :: (1 :: 4 :: ø) :: (1 :: 3 :: 4 :: ø) :: (1 :: 2 :: 3 :: ø) :: (1 :: 2 :: 4 :: ø) :: (1 :: 2 :: 3 :: 4 :: ø) :: ø PS: hd(k) ist das erste Element einer nicht-leeren Liste k und tl(k) entsteht aus k durch Löschen von hd(k). '<>' bezeichnet Listenkonkatenation.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.22, eingetragen 2021-10-19

In Python sollte das wohl so etwas sein: \sourceon Python \numberson from typing import List, Tuple def prefix(e: int, M: List[List]) -> List[List]: return [[e] + S for S in M] def potenz_menge(S:List) -> List[List]: if not S: return [[]] tail = potenz_menge(S[1:]) return prefix(S[0],tail) + tail def potenz_liste(S:List[Tuple[int,int]]) -> List[List[Tuple[int,int]]]: if not S: return [[]] tail = potenz_liste(S[1:]) e,m = S[0] return sum((prefix((e,i),tail) for i in range(1,m+1)),start=tail) pm = potenz_menge([1,2,3,4]) print(f"{len(pm)=}") print(pm) pl = potenz_liste([(2,3),(3,2),(5,1),(7,2)]) print(f"{len(pl)=}") print(pl) \sourceoff und in Javascript könnte man es so versuchen: \sourceon html \numberson Potenzmenge

Potenzmenge von [1,2,3,4]

Potenzliste von [[2,3],[3,2],[5,1],[7,2]]

\sourceoff



   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.23, eingetragen 2021-10-20

\quoteon(2021-10-19 18:33 - DerEinfaeltige in Beitrag No. 22) In Python sollte das wohl so etwas sein: ... \quoteoff - Wozu braucht man 'potenz_menge' und was ist die Potenzmenge einer Liste? - Was macht 'potenz_liste'? - Hast Du die Performance dieses Algorithmus mit Deinem vorherigen Algorithmus verglichen und was ist das Ergebnis?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.24, eingetragen 2021-10-20

\quoteon(2021-10-20 18:10 - Zwerg_Allwissend in Beitrag No. 23) - Wozu braucht man 'potenz_menge' und was ist die Potenzmenge einer Liste? \quoteoff Komische Frage, du wolltest doch eine Hilfsfunktion zum Erstellen der Potenzmenge, also der Menge der Teillisten?!? Diese habe ich übersetzt und leicht korrigiert. - Der Rekursionsanker sollte wohl \(\{\emptyset\}\) zurückgeben und nicht \(\emptyset\)?!? - Der Wert von ℘ℓ(tl(k)) sollte zwischengespeichert und nicht jedes Mal neu berechnet werden. \quoteon(2021-10-20 18:10 - Zwerg_Allwissend in Beitrag No. 23) - Hast Du die Performance dieses Algorithmus mit Deinem vorherigen Algorithmus verglichen und was ist das Ergebnis? \quoteoff Da Potenzmengen/Listen aller Teillisten für Primfaktoren höherer Multiplizität zu vielen Dubletten führen, sind sie dort ungeeignet. Erzeugt man keine Dubletten (das macht die Variante potenz_liste), so erhält man die rekursive Version meines Algorithmus und dementsprechend eine bis auf eine kleine Konstante vergleichbare Laufzeit. \sourceon Python \numberson from typing import List, Tuple def prefix(e: int, M: List[List]) -> List[List]: return [[e] + S for S in M] print(f"{prefix(1,[[2,3],[3],[2,3,4]])=}") def potenz_menge(S:List) -> List[List]: if not S: return [[]] tail = potenz_menge(S[1:]) return prefix(S[0],tail) + tail print(f"{potenz_menge([1,2,3])=}") def produkt(S:List[int]) -> int: p = 1 for f in S: p *= f return p print(f"{produkt([1,2,3,4])=}") def expand(pair:Tuple[int,int]) -> List[int]: p,e = pair return [p]*e print(f"{expand((2,3))=}") def teiler(S:List[Tuple[int,int]]) -> List[int]: S = sum((expand(pair) for pair in S),start=[]) P = potenz_menge(S) return sorted(set(produkt(p) for p in P)) print(f"{teiler([(2,3),(3,2)])=}") \sourceoff


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.25, eingetragen 2021-10-20

\quoteon(2021-10-20 20:07 - DerEinfaeltige in Beitrag No. 24) \quoteon(2021-10-20 18:10 - Zwerg_Allwissend in Beitrag No. 23) - Wozu braucht man 'potenz_menge' und was ist die Potenzmenge einer Liste? \quoteoff Komische Frage, ... \quoteoff Es gibt keine komischen Fragen, nur komische Antworten. \quoteon du wolltest doch eine Hilfsfunktion zum Erstellen der Potenzmenge, also der Menge der Teillisten?!? \quoteoff Nein, mein Algorithmus berechnet die Liste (und nicht die Menge) aller Teillisten. Potenzmengen kommen in meinem Ansatz überhaupt nicht vor. \quoteon Diese habe ich übersetzt und leicht korrigiert. - Der Rekursionsanker sollte wohl \(\{\emptyset\}\) zurückgeben und nicht \(\emptyset\)?!? \quoteoff Kann man machen, ist aber egal, da das Argument von ℘ℓ in der intendierten Anwendung die Liste aller Primfaktoren einer nat. Zahl n ≥ 2 ist, und diese Primfaktorlisten sind nicht leer. Für function ℘ℓ*(k : list[@ITEM]) : list[list[@ITEM]] <= if ?ø(k) then ø :: ø else if ?ø(tl(k)) then (hd(k) :: ø) :: ø else (hd(k) :: ø) :: (℘ℓ*(tl(k)) <> hd(k) ⊕ ℘ℓ*(tl(k))) end_if end_if gilt ∀ k : list[@ITEM] k ≠ ø → ℘ℓ(k) = ℘ℓ*(k) \quoteon - Der Wert von ℘ℓ(tl(k)) sollte zwischengespeichert und nicht jedes Mal neu berechnet werden. \quoteoff Dann verwende eben function ℘ℓ(k : list[@ITEM]) : list[list[@ITEM]] <= if ?ø(k) then ø else if ?ø(tl(k)) then (hd(k) :: ø) :: ø else let l := ℘ℓ(tl(k)) in (hd(k) :: ø) :: (l <> hd(k) ⊕ l) end_let end_if end_if \quoteon Da Potenzmengen/Listen aller Teillisten für Primfaktoren höherer Multiplizität zu vielen Dubletten führen, sind sie dort ungeeignet. \quoteoff Ja, die Dubletten stören. Aber diese im Potenlistenalgorithmus abzufangen ist kompliziert und führt schnell zu Fehlern. Sauberer ist es diese in einem nachfolgenden Schritt mittels function purge(k : list[@ITEM]) : list[@ITEM] <= if ?ø(k) then ø else if hd(k) ∈ tl(k) then purge(tl(k)) else hd(k) :: purge(tl(k)) end_if end_if zu eliminieren. Damit kann man dann ∀ n : ℕ, k : list[ℕ] k ∈ purge(℘ℓ(ℙf(n))) → ∏(k) ∣ n beweisen. \quoteon Erzeugt man keine Dubletten (das macht die Variante potenz_liste), so erhält man die rekursive Version meines Algorithmus und dementsprechend eine bis auf eine kleine Konstante vergleichbare Laufzeit. \quoteoff Zeigt doch mal eine Tabelle, die die Laufzeiten vergleicht und dabei auch zeigt, daß die Ergebnisse beider Verfahren identisch sind.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.26, eingetragen 2021-10-21

\quoteon(2021-10-20 22:22 - Zwerg_Allwissend in Beitrag No. 25) Zeigt doch mal eine Tabelle, die die Laufzeiten vergleicht und dabei auch zeigt, daß die Ergebnisse beider Verfahren identisch sind. \quoteoff Keine Zeit und Kompetenz. Mach das doch bitte selbst!


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.27, eingetragen 2021-10-21

\quoteon(2021-10-21 11:19 - DerEinfaeltige in Beitrag No. 26) \quoteon(2021-10-20 22:22 - Zwerg_Allwissend in Beitrag No. 25) Zeigt doch mal eine Tabelle, die die Laufzeiten vergleicht und dabei auch zeigt, daß die Ergebnisse beider Verfahren identisch sind. \quoteoff Keine Zeit und Kompetenz. Mach das doch bitte selbst! \quoteoff Honi soit qui mal y pense - ist halt nicht so einfach wie es zunächst ausschaut ...


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.28, vom Themenstarter, eingetragen 2021-10-25

\quoteon(2021-10-19 15:20 - Zwerg_Allwissend in Beitrag No. 21) \quoteon (1) ℙf(n) := Liste aller Primfaktoren von n (wenn n ≥ 2) (2) ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n) (3) P(℘ℓ(ℙf(n))) := die Menge aller Produkte der Elemente der Listen in ℘ℓ(ℙf(n)) P(℘ℓ(ℙf(n))) ist dann die Menge aller Teiler von n (inklusive n). \quoteoff ➩ ℘ℓ(1 :: 2 :: 3 :: 4 :: ø) ➲ (1 :: ø) :: (2 :: ø) :: (3 :: ø) :: (4 :: ø) :: (3 :: 4 :: ø) :: (2 :: 3 :: ø) :: (2 :: 4 :: ø) :: (2 :: 3 :: 4 :: ø) :: (1 :: 2 :: ø) :: (1 :: 3 :: ø) :: (1 :: 4 :: ø) :: (1 :: 3 :: 4 :: ø) :: (1 :: 2 :: 3 :: ø) :: (1 :: 2 :: 4 :: ø) :: (1 :: 2 :: 3 :: 4 :: ø) :: ø \quoteoff ich versuche gerade herauszufinden, was ℘ℓ für ascii Zeichen sind 🙃 ich habe ein array \sourceon php


   Profil
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 470
Wohnort: Deutschland
  Beitrag No.29, eingetragen 2021-10-25

\quoteon(2021-10-25 00:56 - juergenX in Beitrag No. 28) Wieviel echt verschieden Dupels, tripels up to 7-tupels gibt es? Es gibt anscheinend 9 echt verschieden Dupels. Anzahl der Tripels ist eben nicht =$\binom{8}{3}$, sondern weniger. Und wie ist die Ausgabe bzw. Programmiereung in Python oder php von Make_all_Different_lists (allbases, AllExponents). Das ist nicht so trivial wie ℘ℓ(ℙf(n)) := die Liste aller Teillisten von ℙf(n). \quoteoff Wenn mich nicht alles täuscht, leistet das mein Algorithmus aus Beitrag 3 schon. Da wird bereits ein Array mit allen eindeutigen Teilerlisten ausgegeben. Wenn man sie nach der Länge filtert, bekommt man die Tripel, Dupel usw. Wenn man alle Vorkommnisse inklusive der doppelten haben möchte, muss man nur die Bedingung streichen, die Duplikate eliminiert. Man kann sie dann später in einem Set zusammenstampfen. Das hier würde die Tupel ausgeben: \sourceon JavaScript dividers.filter(a=>a.length==2).length \sourceoff Wie auch immer: Du hast immer noch nicht gesagt wie deine Zahlen aussehen. Falls du mit Zahlen wie 2^2000 arbeitest, musst du zwangsweise andere Konzepte anwenden, als wenn es nur um kleinere Zahlen geht.


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 458
  Beitrag No.30, vom Themenstarter, eingetragen 2021-10-30

\quoteon(2021-10-25 02:58 - Scynja in Beitrag No. 29) Das hier würde die Tupel ausgeben: \sourceon JavaScript dividers.filter(a=>a.length==2).length \sourceoff Wie auch immer: Du hast immer noch nicht gesagt wie deine Zahlen aussehen. Falls du mit Zahlen wie 2^2000 arbeitest, musst du zwangsweise andere Konzepte anwenden, als wenn es nur um kleinere Zahlen geht. \quoteoff Zahlen mit nur einer Basis b^n sind ja leicht zu analysieren. sogar $2^{2000}$. divisors (2^{2000}) = 2^{1,2,3,..1999} Mein Beispiel mit 4 verschiedenen Base und verschiedene Exponenten $2^3*3^2*5*7^2$ erfordert, wie du ja auch sagtest Bildung von Teillisten, die sehr aufwendig ist. Kommt also zu einem andern beliebigem b^n noch eine Basis c^m dazu: $X=b^n*c^m$, so wird die Sache schon komplexer. Hat man einen Teiler wie auch immer der Art $c^m$ gefunden, so kennen wir auch alle $c,c^2,c^3\dotsc^{m-1}$ Bsp $2^6*3^7 = 139968$ $\lfloor\sqrt{139968}\rfloor= 374$. Der naechsttiefere Teiler als Primzahlpotenz unter 374 ist schon $343= 3^5$. Und dann $2^8 = 256$. Und fertig. weil $139968/(3^5*2^8)=1$. Das waere eine effektive Primzahlzerlegung, wenn man möglichst viel Primzahlpotenzen kleinerer Zahlen kennt. Und alle Divisoren um die es ja geht sind: $\prod\nolimits_{i=0}^8 x_i 2^i * \prod\nolimits_{j=0}^5 x_i 3^j$. Diese Methode wird langsamer je mehr Basen der Dividend enthält oder etwa nur $a*b$ bei sehr hohem X ist, oder prime. Ich hab noch nicht gechecked, was die optimale Methode für alle $n\in N$ mit/ohne Kenntnis der PfZ ist.


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 279
  Beitrag No.31, eingetragen 2021-10-31

Ich habe mir die Sache nochmal angeschaut: Die Primfaktorzerlegung einer natürlichen Zahl n wird idealerweise durch eine Multimenge ℙf(n) repräsentiert. "Multi" weil identische Primzahlen in ℙf(n) mehrfach vorkommen können, "Menge" weil die Reihenfolge, in der Primzahlen in ℙf(n) eingefügt werden, keine Rolle spielt. Der Einfachheit halber werden ℙf(0) und ℙf(1) als leere Multimenge definiert. Multimengen können mittels Listen implementiert werden. Für Multimengen k und l (implementiert durch Listen) gilt k ⊂ l gdw. jedes Vorkommen eines Elements in k ein eigenes Vorkommen in l hat. D.h., z.B. <2, 2, 3> ⊂ <2, 5, 2, 3, 2> und <1, 2> ⊂ <2, 1>. Ausgangspunkt für die Bestimmung aller Teiler einer natürlichen Zahl ist (1) ∀ k, l : list[ℕ] ℙℓ(k) ∧ ℙℓ(l) ∧ k ⊂ l → ∏(k) ∣ ∏(l) sowie (2) ∀ k, l : list[ℕ] ℙℓ(k) ∧ ℙℓ(l) ∧ ∏(k) ∣ ∏(l) → k ⊂ l wobei ℙℓ(k) gilt gdw. jedes Element von k eine Primzahl ist. Mit (3) ∀ x : ℕ x ≠ 0 → ∏(ℙf(x)) = x folgt daraus (4) ∀ n, m : ℕ n ≠ 0 ∧ m ≠ 0 ∧ ℙf(n) ⊂ ℙf(m) → n ∣ m sowie (5) ∀ n, m : ℕ n ≠ 0 ∧ m ≠ 0 ∧ n ∣ m → ℙf(n) ⊂ ℙf(m) oder umgeformt (5) ∀ m : ℕ, k : list[ℕ] k € ℘ℓ(ℙf(m)) → ∏(k) ∣ m sowie (6) ∀ m : ℕ, k : list[ℕ] m ≠ 0 ∧ ∏(k) ∣ m → k € ℘ℓ(ℙf(m)) wobei ℘ℓ(l) die Menge (nicht Multimenge!) aller Teilmultimengen (bzgl. ⊂) der Multimenge l ist. Damit erhält man genau alle Teiler von m ≠ 0 mittels der Produkte der Multimengen in ℘ℓ(ℙf(m)). Beispielsweise gilt ℙf(12) = <2, 2, 3> und folglich ℘ℓ(ℙf(12)) = {ø, <2>, <3>, <2, 2>, <2, 3>, <2, 2, 3>}. Da Multimengen jedoch mittels Listen implementiert werden, kann nicht die Elementrelation ∈ für Listen verwendet werden: Für Listen l gilt i ∈ l gdw. l = <..., i, ...>, also z.B. 2 ∈ <1, 2, 3>, aber nicht <3, 2> ∈ ℘ℓ(ℙf(12)). Es darf also nicht die Identität = verwendet werden, sondern man muß die Elementbeziehung mittels der Multimengengleichheit ≈ definieren: Es gilt k € ℘ℓ(l) gdw. ℘ℓ(l) = {..., k', ...} und k ≈ k'. Da Multimengen hier durch Listen implementiert werden, gilt k ≈ k' gdw. die Liste k' eine Permutation der Liste k ist. Die Menge aller Teilmultimengen einer Multimenge kann wie folgt berechnet werden: function ℘ℓ(k : list[@ITEM]) : list[list[@ITEM]] <= if ?ø(k) then ø :: ø else let pl := ℘ℓ(tl(k)) in pl ∪ hd(k) ⊕ pl end_let end_if mit function [infix] ⊕(i : @ITEM, K : list[list[@ITEM]]) : list[list[@ITEM]] <= if ?ø(K) then ø else (i :: hd(K)) :: (i ⊕ tl(K)) end_if so daß (7) ∀ k, l : list[@ITEM] k € ℘ℓ(l) → k ⊂ l sowie (8) ∀ k, l : list[@ITEM] k ⊂ l → k € ℘ℓ(l) bewiesen werden kann. Für eine gegebene Primfaktorzerlegung k erhält damit man ein korrektes (=> das Produkt jeder Multimenge in ℘ℓ(k) ist Teiler von ∏(k)) und vollständiges (=> die Primfaktorzerlegung jedes Teilers von ∏(k) ist in ℘ℓ(k) enthalten) Verfahren zur Bestimmung aller Teiler von ∏(k). Neben ℘ℓ und ⊕ benötigt man zur Implementierung nur noch function [infix] ∈(i : @ITEM, k : list[@ITEM]) : bool <= if ?ø(k) then false else if i = hd(k) then true else i ∈ tl(k) end_if end_if und function [infix] ∪(k : list[@ITEM], l : list[@ITEM]) : list[@ITEM] <= if ?ø(k) then l else if hd(k) ∈ l then tl(k) ∪ l else hd(k) :: (tl(k) ∪ l) end_if end_if ist also insgesamt nur wenig Programmcode. Die Repräsentation von Mengen durch Listen kann entfallen, wenn man das Verfahren in einer Sprache implementiert, die Mengenoperationen zur Verfügung stellt. Allerdings ist dies nur sinnvoll, wenn dort Mengenoperationen auch effizient realisiert sind. Gleiches gilt im Prinzip für Multimengen, nur kenne ich keine diesbzgl. Programmiersprache. Für das Eingangsbeispiel $\displaystyle 2^3*3^2*5*7^2 = 17640$ wird die Multimenge der Primfaktoren durch die Liste <2, 2, 2, 3, 3, 5, 7, 7> (oder eine beliebige Permutation davon) repräsentiert. Für Probleme dieser Größenordnung kommt das Verfahren gut damit zurecht. Für größere Aufgaben ist es vorteilhaft Multimengen als Menge M von Paaren [b, n] zu implementieren, wobei n ≠ 0 die Anzahl der Vorkommen von b in der Multimenge M angibt. Die Kardinalität der Menge ℘(M) aller Teilmultimengen von M ändert sich dadurch nicht (das exponentielle Wachstum kann man natürlich nicht loswerden), aber die Operationen zur Bestimmung von ℘(M) können effizienter implementiert werden. Beispielsweise sind | k | ∈-Vergleiche bei Berechnung von k ∪ l erforderlich während man bei der Paar-Repräsentation lediglich die Anzahl der Vorkommen der Elemente in k und l addieren muß, d.h. für [b, n] € k und [b, m] € l gilt dann [b, n + m] € k ∪ l, wobei [b, i] € k gdw. k = {..., [b, j], ...} und i ≤ j.


   Profil
juergenX hat die Antworten auf ihre/seine Frage gesehen.
juergenX hatte hier bereits selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]