Die letzten 4 Beiträge |
eulerscheZahl |
Allgemein braucht der Algorithmus Summe(Teiler)-Anzahl(Teiler) modulo-Divisionen
Für N=2^n * (2^n-1) und (2^n-1) als Primzahl sind das 2*n+(2^n-1)-(n+1) = 2^n+n-2 Schritte.
Nach etwas Termumformung (ich hoffe, ich habe mich nicht verrechnet):
für die 56 kommt da übrigens 9 raus, nicht 8. Für den letzten Faktor müss von 2-7 die modulo-Operation 6 mal ausgeführt werden.
f(127*128) = 133 ist der nächste Wert der Folge, da 63 nicht prim ist.
Unterm Strich bleibt festzustellen, dass es deutlich bessere Algorithmen zur Faktorisierung gibt. |
zteve |
Hallo,
Danke für die Antwort.
Hab mir das nohcmal durch den Kopf gehen lassen. Meine Formel log(n+1) + n-2 macht nur bedingt Sinn.
n wäre hier quasi bei 56, die 7 --> 2*2*2*7=56 und 8 * 7 = 56. Also der Primzahlfaktor, der nach den 2ern kommt.
Zusätzliche Bedingung, dass die Formel log(n+1) + n-2 stimmt ist aber dann auch, dass n genau eins weniger ist, als das Produkt der 2er ergibt.
Also Beispiel:
Bei 56 stimmt die formel (8*7 = 56 --> 2*2*2=8 --> 8-1 = 7 --> 8 * (8-1) = 56)
Bei 40 stimmts nicht: (8*5 = 40 ---> 2*2*2 = 8 --> 8-3 = 5 --> 8* (8-3) = 40)
Ich hoffe du versehst, woraus ich hinaus will.
Also die Formel Log(n+1) + (n-2) mit n = der letzte Primfaktor nach den 2er Potenzen gilt nur, wenn sich die Zahl aus 2^x * ((2^x) - 1) zusammensetzen lässt. |
eulerscheZahl |
Ich gebe dir Recht, dass die Lösung falsch ist.
Zitat: |
der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal. |
was soll n sein?
Das schlechteste Verhalten erreichst du, wenn die zu faktorisierende Zahl eine Primzahl ist. Dann brauchst du in NächsterTeiler N-1 Durchläufe. |
zteve |
Zeitaufwand Primfaktorzerlegung
Hallo zusammen,
ich habe ein Verständnisproblem mit der Lösung, die wir bekommen haben bezüglich des Zeitaufwands zu folgendem Algorithmus:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
|
Eingabe N: Natürliche Zahl
Ausgabe PrimFak: Menge der Prim-Faktoren von N
PrimFak := {};
While N>1 do
NächsterTeiler (N,T)
N := N/T Füge T zu PrimFak
Funktion NächsterTeiler (Eingabe: N, Ausgabe:T)
T:=2
While N mod T != 0 do T:= T+1
|
|
Bezüglich des Zeitaufwands ist folgende Lösung angegeben:
Rechenzeitaufwand für Nächster Teiler ist beim ersten Aufruf höchstens N,
beim zweiten Aufruf durch Teilen des Faktors N/T < N/2
beim dritten Aufruf durch weiteres Teilen N/T /T´ < N/2 /2 = N/4
Insgesamt höchstens N* (1 + ½ + ¼ + ..) < N*2 .
Ich meine aber, dass das falsch ist:
Wenn "NächsterTeiler" den Rechenzeitaufwand von N hat, dann gibt es keinen zweiten Aufruf von "NächsterTeiler" da, durch das Teilen dann N/T = 1 herauskommen würde. Das beim 2. Aufruf maximal N/2 Schritte benötigt werden setzt voraus, dass N halbiert wurde, also der 1. Aufruf 1 Schritt und nicht N Schritte gebraucht wurde, sondern der Teiler 2 die Liste halbiert.
Somit würde ich sagen, der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal.
Beispiel: anhand 56:
1. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt)
2. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt)
3. Primfaktor 2 (Durchlauf Nächster Teiler 1 Schritt)
4. Primfaktor 7 (Durchlauf Nächster Teiler 5 Schritte)
Macht insgesamt: 3 + 5 = 8 Schritte bzw. log(8) + 7-2 = 8
Habe ich hier etwas übersehen, oder wie soll ich nun diese Musterlösung interpretieren? |
|
|