nsz Git - libfirm/blob - ir/be/test/SieveBits.c

   1 //
   2 // GCC-firm Project
   3 //
   4 // $Id$
   5 //
   6
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <time.h>
  10
  11 typedef int boolean;
  12
  13 typedef struct BitSet
  14 {
  15     int *P;
  16     int K;
  17 } BitSet;
  18
  19 static void ctorBitSet(BitSet *pThis, int k)
  20 {
  21     pThis->P = (void *)malloc(sizeof(*(pThis->P)) * (k / 32 + 1));
  22     pThis->K = k;
  23 }
  24
  25 static void set (BitSet *pThis, int i)
  26 {
  27     if (i < 0)
  28         return;
  29     pThis->P[i >> 5] |= (1 << (i & 0x0000001F));
  30 }
  31 static void clear (BitSet *pThis, int i)
  32 {
  33     pThis->P[i >> 5] &= ~(1 << (i & 0x0000001F));
  34 }
  35
  36 static boolean get (BitSet *pThis, int i)
  37 {
  38     return (pThis->P[i >> 5] & (1 << (i & 0x0000001F))) != 0;
  39 }
  40
  41 static int size (BitSet *pThis)
  42 {
  43     return pThis->K;
  44 }
  45
  46
  47 /* Sieve.c
  48 Das Primzahlsieb fuer C.
  49 */
  50
  51 static BitSet prime;
  52 // Enthaelt Flags fuer die ungeraden Zahlen:
  53 // 3,5,7,...
  54 // D.h., 2*i+3 ist prim, wenn prime[i] war ist
  55
  56 static void sieve (void) {
  57 // das Sieb
  58     int k = size(&prime), i, j, p, l;
  59     // Zuerst alle Zahlen auf prim setzen
  60     for (i = 0; i < k; i++)
  61         set(&prime, i);
  62     // Dann Vielfache von Primzahlen aussieben
  63     for (i = 0; i < k; i++) {
  64         if (get(&prime, i)) {
  65             // 2*i+3 ist prim
  66             p = 2 * i + 3;
  67             l = (p * p - 3) / 2;
  68             if (l > k)
  69                 break;
  70             for (j = l; j < k; j += p)
  71                 clear(&prime, j); // streicht p*p,p*(p+2), etc.
  72         }
  73     }
  74 }
  75
  76 int main (int argc, char *argv[]) {
  77     // Hauptprogramm
  78     int n, i, k, count;
  79
  80     if (argc <= 1)
  81         n = 10000000;
  82     // falls keine Argumente in der Kommandozeile
  83     else
  84         n = atoi(argv[1]);
  85     // lies Anzahl aus der Kommandozeile
  86     k = (n - 3) / 2;
  87     printf("Counting primes up to %d.\n", (2 * k + 3));
  88
  89     ctorBitSet(&prime, k);
  90     sieve(); // das Sieb
  91
  92     // Zaehle gefundene Primzahlen:
  93     count = 1;
  94     for (i = 0; i < k; i++)
  95         if (get(&prime, i))
  96                 count++;
  97     // Ausgabe:
  98     printf("%d primes found.\n", count);
  99
 100     // list(); // nur fuer Testzwecke
 101     return 0;
 102 }