19 static void ctorBitSet(BitSet *pThis, int k)
21 pThis->P = (void *)malloc(sizeof(*(pThis->P)) * (k / 32 + 1));
25 static void set (BitSet *pThis, int i)
29 pThis->P[i >> 5] |= (1 << (i & 0x0000001F));
31 static void clear (BitSet *pThis, int i)
33 pThis->P[i >> 5] &= ~(1 << (i & 0x0000001F));
36 static boolean get (BitSet *pThis, int i)
38 return (pThis->P[i >> 5] & (1 << (i & 0x0000001F))) != 0;
41 static int size (BitSet *pThis)
48 Das Primzahlsieb fuer C.
52 // Enthaelt Flags fuer die ungeraden Zahlen:
54 // D.h., 2*i+3 ist prim, wenn prime[i] war ist
56 static void sieve (void) {
58 int k = size(&prime), i, j, p, l;
59 // Zuerst alle Zahlen auf prim setzen
60 for (i = 0; i < k; i++)
62 // Dann Vielfache von Primzahlen aussieben
63 for (i = 0; i < k; i++) {
70 for (j = l; j < k; j += p)
71 clear(&prime, j); // streicht p*p,p*(p+2), etc.
76 int main (int argc, char *argv[]) {
82 // falls keine Argumente in der Kommandozeile
85 // lies Anzahl aus der Kommandozeile
87 printf("Counting primes up to %d.\n", (2 * k + 3));
89 ctorBitSet(&prime, k);
92 // Zaehle gefundene Primzahlen:
94 for (i = 0; i < k; i++)
98 printf("%d primes found.\n", count);
100 // list(); // nur fuer Testzwecke