Systemnahe Programmierung in Chome Systemnahe Programmierung in C: Primzahl-Test Prof. Dr. Uwe Schmidt FH Wedel

Primzahl-Test

weiter

weiter


Das Sieb des Eratosthenes implementiert mit Bitoperationen

   1#include <stdio.h>
   2#include <stdlib.h>
   3#include <errno.h>
   4#include <limits.h>
   5
   6/* ---------------------------------------- */
   7
   8typedef unsigned long int Nat0;
   9
  10#define formatNat0     "%lu"
  11#define format10Nat0 "%10lu "
  12
  13/* ---------------------------------------- */
  14
  15typedef unsigned int Set;
  16
  17#define SLEN (CHAR_BIT * sizeof (Set))
  18
  19#define empty ((Set)0)
  20#define full (~empty)
  21#define single(i) ((Set)<< (i))
  22
  23/* ---------------------------------------- */
  24
  25typedef Set * ArrayOfSets;
  26
  27/* dangerous macros !!! */
  28
  29#define remove(se) (s[(e) / SLEN] &= ~ single((e) % SLEN))
  30#define elem(es) ((s[(e) / SLEN] & single((e) % SLEN)) != 0)
  31
  32/* ---------------------------------------- */
  33
  34ArrayOfSets
  35mkField (Nat0 len)
  36{
  37  Nat0 setWords = (len + SLEN -1) / SLEN;
  38  ArrayOfSets res = malloc (setWords * sizeof (Set));
  39
  40  if (!res)
  41    {
  42      perror ("mkField: can't allocate field");
  43      exit (1);
  44    }
  45
  46  {
  47    Nat0 i;
  48    for (i = 0; i < setWords++i)
  49      res[i] = full;
  50  }
  51
  52  return res;
  53}
  54
  55/* ---------------------------------------- */
  56
  57ArrayOfSets
  58sieveField (ArrayOfSets fieldNat0 len)
  59{
  60  Nat0 i;
  61
  62  remove(field, 0);
  63  remove(field, 1);
  64
  65  for (i = 2; i < len++i)
  66    if (elem(ifield))
  67      {
  68        Nat0 j;
  69        for (j = 2 * ij < lenj += i)
  70          remove(fieldj);
  71      }
  72
  73  return field;
  74}
  75
  76/* ---------------------------------------- */
  77
  78#define LL 100
  79
  80void
  81writeField (ArrayOfSets fieldNat0 len)
  82{
  83  Nat0 i;
  84  for (i = 0; i < len++i) {
  85
  86    if (i % LL == 0)
  87      printf(format10Nat0i);
  88
  89    printf (elem(i,field) ? "X" : ".");
  90
  91    if (i % LL == LL -1)
  92      printf("\n");
  93  }
  94  printf("\n");
  95}
  96
  97/* ---------------------------------------- */
  98
  99int
 100main (int argcchar *argv[])
 101{
 102
 103  Nat0 len;
 104  ArrayOfSets field;
 105
 106  sscanf (argv[1]formatNat0&len);
 107  field = mkField (len);
 108
 109  writeField (sieveField (fieldlen)len);
 110
 111  free (field);
 112
 113  return 0;
 114}
weiter

weiter

Übersetzen

cc -o sieb -Wall sieb.c

weiter

weiter

Testen: 10^3

time -p ./sieb 1000

weiter

weiter

Testen: 10^6

time -p ./sieb 1000000

weiter

weiter

Testen: 10^7

time -p ./sieb 10000000

weiter

weiter

Testen: 10^8 (Vorsicht)

time -p ./sieb 100000000

weiter

weiter

Testen: 10^9 (Vorsicht)

time -p ./sieb 1000000000

weiter

weiter

Testen: 10^12 (Vorsicht)

time -p ./sieb 1000000000000

weiter

weiter

Download

Quellen

Letzte Änderung: 17.11.2010
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel