Primfaktorzerlegung läuft viel zu langsam...

[Chris P]

@MatWur:

Erkennt der Compiler also beim Kompilieren das x nicht verändert wird!?
Kann man das irgendwie nachlesen?

[MatWur]

ja, das erkennt der Compiler. Auszug aus der Delphi Language Reference:

Zitat von Delphi Language Reference:

For purposes of controlling execution of the loop, the expressions initialValue and finalValue are evaluated only once, before the loop begins.

danach folgt noch die Erklärung, das dies der wesentlichste Unterschied zur Repeat- und While-Schleife ist.

mfg

Matthias

[Chris P]

@MatWur:

Toll! Jetzt habe ich auch wieder was dazugelernt!

Danke...

[xZise]

Außerdem wäre es möglich gewesen den Wert einmal in eine Variable zu schreiben

PS: Irgendwie komme ich mit der Erklärung nicht da, weil eine solche Schleife funzt:

Delphi-Quellcode:

j := 2;
for i := 0 to j do
  j := j + 1;

Und er würde da nie rausspringen (außer i ist zu groß )

[MatWur]

die angegebene Schleife funktioniert zwar, aber die Schleife wird exakt 3 mal durchlaufen, für i=0, i=1 und i=2. Der Endwert der Schleife (j=2) wird innerhalb der Schleife *nicht* verändert obwohl die Variable geändert wird. Aber der geänderte Variablenwert wird nicht als neuer Endwert der Schleife eingesetzt.

Zitat von xZise:

Außerdem wäre es möglich gewesen den Wert einmal in eine Variable zu schreiben

genau das wird getan in eine eigene Variable für den Endwert die du dann nicht mehr siehst oder ändern kannst.

mfg

Matthias

[xZise]

Selstam.... es ging mal ... naja vielleicht täushce ich mich xD

[fLaSh11]

Das hier ist ein sauschneller Code für eine Primfaktorzerlegung:
(ist halt Konsole, aber mit sehr wenig Arbeitsaufwand umzuwandeln...)

Delphi-Quellcode:

label
  lbl1,lbl2,lbl3,lbl4,lbl5,lbl6,lbl7,lbl8,lbl9;

var
  a,b: Integer;
  c: Extended;

begin
goto lbl2;

lbl1:
writeln('2');
a:=a div 2;
if a=1 then goto lbl9;

lbl2:
if frac(a/2)=0 then goto lbl1;
b:=3;

lbl3:
c:=sqrt(a)+1;

lbl4:
if b>=c then goto lbl8;
if frac(a/b)=0 then goto lbl6;

lbl5:
b:=b+2;
goto lbl4;

lbl6:
if a/b*b-a=0 then goto lbl7;
goto lbl5;

lbl7:
writeln(IntToStr(b));
a:=a div b;
goto lbl3;

lbl8:
writeln(IntToStr(a));

lbl9:
readln;

(ist unübersichtlich aber schnell)

//Edit1: Ich hab vergessen zu erwähnen, dass a die zu zerlegende Zahl ist!
//Edit2: Weiß jemand, ob ich das veröffentlichen darf, denn es war im Handbuch meines GTRs in Basic abgedruckt, habs eig. nur in Delphi verwandelt

[Yamato]

Das kann man sogar noch verbessern: alle Primzahlen außer 2 und 3 sind von der Form 6n+-1 (dadurch werden alle Vielfachen von 3 eliminiert).

Eine kurze Erklärung einiger besserer Verfahren sowie ein Java-Applet gibt's hier:
http://www2.informatik.hu-berlin.de/~schoenbe/

Wer Lust auf Theorie hat, kann das ja mal in Delphi umsetzen.

[alzaimar]

Zitat von fLaSh11:

Das hier ist ein sauschneller Code für eine Primfaktorzerlegung:

Na dann googel mal nach dem 'Sieve of Atkins'. Das findet alle Primzahlen bis 2^32 in ca. 1 Sekunde

Zitat von fLaSh11:

//Edit2: Weiß jemand, ob ich das veröffentlichen darf, denn es war im Handbuch meines GTRs in Basic abgedruckt, habs eig. nur in Delphi verwandelt

Ja, es ist banal und wird Keinen interessieren.

[marabu]

Hallo alzaimar,

Atkins ist der Halbgott mit der Gitarre, der Mathematiker heißt Atkin *grin*

Es gibt ein ausgefeiltes Sieve of Eratosthenes, welches für den 32-bit Zahlenraum eine gute bzw. bessere Wahl ist. Das Sieve of Atkin trumpft jenseits dieser Grenze auf, wenn ich richtig gelesen habe.

Noch ein Link: High Speed Factoring

Gute Nacht