Unbenommen, wenn man den Aufwand für die Oberfläche mitrechnet ist Deine Version bestimmt schneller, aber meine Intention war erst einmal eine einfache Implementierung zur Verfügung zu stellen.
Hier wäre der nächste Schritt bestimmt, die geraden Zahlen(2) aus der Berechnung zu eliminieren.
Gruß
K-H
Nee, die ist nicht nur dann schneller, wenn man den Aufwand für die Oberfläche mitrechnet.
Du schriebst 15-16 für 250M, ich maß 600ms für 250M also um den Faktor 25 schneller.
Aber das nur nebenbei - meine Version ist recht unoptimiert, und deshalb für meine Begriffe bummelig.
Horst hat ja einen Link reingestellt auf eine wirklich schnelle Version.
Und der nächste Schritt, die geraden Zahlen zu eleminieren ist eigentlich einfach.
In etwa so:
Mit CreateSieve(250000000); wird zum Beispiel ein Sieb für 1..250M erstellt.
Mit AIsPrime(N) kann man dann für Zahlen im Bereich des Siebs feststellen, ob N prim ist.
Delphi-Quellcode:
var
PSieve:Pointer;
LastBit:NativeUInt;
FUNCTION AClearMultiples(P:NativeUInt):NativeUInt;
asm // In : EAX==P
mov ecx,LastBit;
mov edx,PSieve;
push ebx
// EBX retten
mov ebx,eax
// V:=P
imul ebx,eax
// V:=P^2
shr ebx,1
// Bit Nr. für P^2
@ClearLoop:
// Alle Vielfachen von P = 0 setzen
btr [edx],ebx
// PData[V]:=0;
add ebx,eax
// V:=V+2P
cmp ebx,ecx
// V<=Max
jbe @ClearLoop
// ja, weiter
pop ebx
// EBX restaurieren
// Nächstes 1 Bit suchen
shr eax,1
// Bit Nr für P
@NextLoop: add eax,1
// P:=P+2
bt [edx],eax
// PData[P]=1?
jnc @NextLoop
// nein weiter suchen
lea eax,[eax*2+1]
// Nächstes P
end;
PROCEDURE CreateSieve(Numbers:NativeUInt);
var Bits,Size,Last,P:NativeUInt;
begin
Bits:=(Numbers
div 2)+(Numbers
and 1);
// = Anzahl ungerader Zahlen 1..Numbers
Size:=Bits
div 8;
// Anzahl Bytes für Bits
if (Bits
and 7)<>0
then Inc(Size);
// Eventuell 1 Byte mehr
LastBit:=Size
shl 3-1;
GetMem(PSieve,Size);
FillChar(PSieve^,Size,$FF);
// alle Bits=1
PByte(PSieve)^:=$FE;
// Bit 0 (entspricht der 1) = 0
Last:=Trunc(Sqrt(Numbers));
// Letztes P deren Vielfache zu löschen sind
P:=3;
while P<=Last
do P:=AClearMultiples(P);
ShowMessage('
Sieb erstellt');
end;
FUNCTION AIsPrime(N:NativeUInt):boolean;
asm // In : EAX=N
cmp eax,2
// 0,1: CF=1, 2:CF=0
jbe @SetRes
// N<=2
shr eax,1
// Bitnr für N (N=even: CF=0)
jnc @ToggleCF
// N>2, even
mov edx,PSieve
bt [edx],eax
@ToggleCF: cmc
// CF:=not CF
@SetRes: setnc al
// N=2:true, N<2:false, N>2,even:false
end;