@Hador,
ich habe interessehalber mal eine Assemblerversion geschrieben, die die Daten in einem Bitfeld speichert.
Das ganze kann man noch optimieren
a) im Prinzip braucht man die Daten nur für ungerade Zahlen speichern weil die einzige gerade natürliche Primzahl 2 ist,
und die kann man ja separat prüfen
b) die Geschwindigkeit kann man sicherlich noch deutlich erhöhen.
hab nicht intensiv getestet...
Delphi-Quellcode:
var sieve:
array of cardinal;
PROCEDURE CreateSieve(max:integer);
var len:integer;
PROCEDURE FillSieve;
asm
pushad
mov edi,sieve
// Adresse sieve[0]
xor [edi],3
// Bit 0 und 1 löschen
mov ebx,[edi-4]
// Länge in Cardinals
shl ebx,5
// Länge in Bits
// ECX = P = Erste ungerade Primzahl
mov ecx,3
mov eax,9
// P^2
// Beginnend bei P*P alle Vielfachen von P als nichtprim markieren
@ClrBitLoop: btr [edi],eax
// Bit löschen
add eax,ecx
// + P
cmp eax,ebx
// noch im gültigen Bereich ?
jb @ClrBitLoop
// ja
// Nächsthöheres P suchen
@NxtPrimeLoop: add ecx,2
// P:=P+2
bt [edi],ecx
// Ist P prim ?
jnc @NxtPrimeLoop
// nein, nächstes P prüfen
mov eax,ecx
// P=Primzahl
mul ecx
// P^2
cmp eax,ebx
// noch im gültigen Bereich
jb @ClrBitLoop
// ja, vielfache als nichtprim markieren
@
End: popad
end;
begin
len:=max
shr 5 + 1;
SetLength(sieve,len);
FillChar(sieve[0],len
shl 2,$AA);
SetLength(sieve,len);
FillSieve;
end;
FUNCTION IsPrime(p:integer):boolean;
asm
mov ecx,sieve
// Adresse sieve
mov edx,[ecx-4]
// Länge in Cardinal
shl edx,5
// Länge in Bits
cmp eax,edx
jb @TestPrime
xor eax,eax
@TestPrime: bt [ecx],eax
setc al
end;