Sehr schneller Primzahl-Finder

[Phantom1]

Zitat von negaH:

Und "div 30" liese sich durch "*(1/30)" ersetzen. Allerdings sollte man so'nen Aufwand wirklich nur in den innersten Schleifen treiben.

Aber man müsste doch das Ergebnis wieder mit Trunc abrunden, was doch letztendlich wieder langsamer wäre, oder?

Zitat von negaH:

MODs[mBit] := 1 shl mBit;
der Shift dürfte auf heutigen Rechnern schneller ausgeführt werden als eine Lookup Tabelle im Speicher.

Das geht leider nicht, da ich hierbei nur die zahlen 7,11,13,17,19,23,29 in das jeweilige Bit(0-7) umrechne und setzte, alle anderen Zahlen werden nicht berücksichtigt.

Zitat von negaH:

was wäre wenn k von Anfang an schon von 0 bis Sqrt(MaxPrime div PrimeBits) laufen würde

PrimeBits ist die anzahl der zahlen in einem Teilarray (64KB=1966080 zahlen). Dieses teilarray wird solange durchlaufen bis maxprime erreicht wurde. Wenn ich k jetzt nur bis zur Wurzel berechne, werden nicht mehr alle Zahlen berechnet.

Zitat von negaH:

Schau dir mal meinen Source genauer an. Er macht ja exakt das gleiche wie der deinige, kommt aber ohne Fließkommazahlen aus und benutzt weniger Divisionen.

Deinen Source hab ich mir bis jetzt noch nicht genauer anschauen können, du scheinst doch einige sachen anders gelöst zu haben und da muss ich mich erstmal reinversetzten. Wenn ich mehr Zeit habe, schaue ich mir den Code mal genauer an.

Was mich jedoch noch interessieren würde, ist wie du die 2,5 sek auf einen P4 1,5GHz gemessen hast? Ich komme da mit einem wesentlich schnelleren CPU auf schlechtere Resultate. Oder hab ich beim messen was falsch gemacht?

Delphi-Quellcode:

procedure TForm1.Button3Click(Sender: TObject);
var counter: TCounter; i,j: Cardinal;
begin
  counter:=TCounter.Create(RealTime);

  i:=primes.IndexOf(1, True);
  j:=primes.IndexOf(500000000, False);

  for i:=i to j do
    primes[i];

  caption:=floattostr(counter.Stop);
  counter.Free;
end;

mfg
Phantom1