Systemnahe Programmierung in C: Primzahl-Test
| Systemnahe Programmierung in C: Primzahl-Test |
|
|
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)1 << (i))
22
23/* ---------------------------------------- */
24
25typedef Set * ArrayOfSets;
26
27/* dangerous macros !!! */
28
29#define remove(s, e) (s[(e) / SLEN] &= ~ single((e) % SLEN))
30#define elem(e, s) ((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 field, Nat0 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(i, field))
67 {
68 Nat0 j;
69 for (j = 2 * i; j < len; j += i)
70 remove(field, j);
71 }
72
73 return field;
74}
75
76/* ---------------------------------------- */
77
78#define LL 100
79
80void
81writeField (ArrayOfSets field, Nat0 len)
82{
83 Nat0 i;
84 for (i = 0; i < len; ++i) {
85
86 if (i % LL == 0)
87 printf(format10Nat0, i);
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 argc, char *argv[])
101{
102
103 Nat0 len;
104 ArrayOfSets field;
105
106 sscanf (argv[1], formatNat0, &len);
107 field = mkField (len);
108
109 writeField (sieveField (field, len), len);
110
111 free (field);
112
113 return 0;
114}
|
|
| Letzte Änderung: 17.11.2010 | © Prof. Dr. Uwe Schmidt |
