Primzahlen von 0 bis n

[Amateurprofi]

@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;