primenums_pc.c
2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/* -----------------------------------------------------------------------------
* Copyright (C) 2019-2021 daiteq s.r.o. http://www.daiteq.com
*
* This program is distributed WITHOUT ANY WARRANTY; without even
* the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
* PURPOSE.
*
* -----------------------------------------------------------------------------
* Filename : primenums_pc.c
* Authors : Martin Danek
* Description : Sieve of Eratosthenes - reference desktop implementation
* Release :
* Version : 1.0
* Date : 27.4.2021
* -----------------------------------------------------------------------------
*/
#include <stdio.h>
#include <stdlib.h>
#define PRINT_ITEMS /* */
#define VERBOSE /*
/* #define LONGRUN /* */
#define MAXNUM 1300000
#define SQRTMAXNUM 1141 // ceil(sqrt(1300000))
// #define MAXNUM 8192 // 1300000
// #define SQRTMAXNUM 92 // 1141 // ceil(sqrt(1300000))
void i_print(unsigned i) {
unsigned char buf[22];
unsigned idx=20;
buf[21]='\0';
// buf[20]='\n';
if (i==0) {
buf[idx--]='0';
}
else {
while ((i>0)&&(idx>0)) {
buf[idx--]='0'+(i%10);
i=i/10;
}
}
buf[idx]=' ';
printf("%s",&buf[idx]);
}
unsigned i_conv(char *s) {
unsigned val=0;
unsigned i=0;
while (*(s+i)!='\0') {
// printf("%c",*(s+i));
val*=10;
val+=*(s+i)-'0';
i++;
}
// printf("\n");
return val;
}
int main(void) {
int i,j;
unsigned sz;
unsigned *a;
// char *a;
unsigned top;
unsigned acc;
sz = sizeof(unsigned);
// sz = sizeof(char);
top = MAXNUM;
if ((a=malloc(top*sz))==NULL) {
printf("primenums: malloc failed for size %u\n",top*sz);
exit(1);
}
printf("primenums: MAXNUM is ");i_print(top);
printf("\n");
// printf("primenums: sizeof(unsigned) is ");i_print(sz);
printf("primenums: sizeof(char) is ");i_print(sz);
printf("\n");
printf("primenums: initializing array\n");
for (i=0;i<top;i++) {
*(a+i)=1;
// i_print(i);
}
printf("primenums: eliminating composites\n");
j=2;
while(j<SQRTMAXNUM) {
while (*(a+j)==0)
j++;
for (i=j;i<top;i=i+j)
if (i>j) {
*(a+i)=0;
}
j++;
}
#ifdef PRINT_ITEMS
#ifdef VERBOSE
printf("primenums: printing primes\n");
#endif
acc=0;
for (i=1;i<top;i++)
#ifdef VERBOSE
if (*(a+i)==1) {
printf("%d\n",i);
acc++;
}
#else
if (*(a+i)==1)
printf("1");
else
printf("0");
#endif
printf("\n");
#endif
printf("primenums: primes found: %d\n\n",acc);
printf("\n*** END OF TEST ***\n");
}