1 |
dashley |
172 |
//$Header$ |
2 |
dashley |
175 |
//******************************************************************************** |
3 |
|
|
//Copyright (c) 2003, 2018 David T. Ashley. |
4 |
|
|
//******************************************************************************** |
5 |
|
|
//This file is part of "arith_large_cgi", a program that is designed to be |
6 |
|
|
//invoked by a PHP script as part of serving a web page that performs |
7 |
|
|
//calculations involving large integers. (A secondary compiled program is |
8 |
|
|
//used because a compiled program can perform certain calculation-intensive |
9 |
|
|
//tasks far more efficiently than a PHP script.) This program is provided by |
10 |
|
|
//David T. Ashley (dashley@gmail.com) under the MIT License (reproduced |
11 |
|
|
//immediately below). |
12 |
|
|
//******************************************************************************** |
13 |
|
|
//Permission is hereby granted, free of charge, to any person obtaining a copy |
14 |
|
|
//of this software and associated documentation files (the "Software"), to deal |
15 |
|
|
//in the Software without restriction, including without limitation the rights |
16 |
|
|
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
17 |
|
|
//copies of the Software, and to permit persons to whom the Software is |
18 |
|
|
//furnished to do so, subject to the following conditions: |
19 |
dashley |
172 |
// |
20 |
dashley |
175 |
//The above copyright notice and this permission notice shall be included in all |
21 |
|
|
//copies or substantial portions of the Software. |
22 |
|
|
// |
23 |
|
|
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
24 |
|
|
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
25 |
|
|
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
26 |
|
|
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
27 |
|
|
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
28 |
|
|
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
29 |
|
|
//SOFTWARE. |
30 |
|
|
//******************************************************************************** |
31 |
|
|
// |
32 |
dashley |
172 |
//Sieve of Eratosthenes Table Generation |
33 |
|
|
//-------------------------------------- |
34 |
|
|
//This utility generates a sieve table used in trial division prime number factorization. |
35 |
|
|
//The table is a table of differentials to be added to trial divisors. |
36 |
|
|
//-------------------------------------------------------------------------------- |
37 |
|
|
#include <stdio.h> |
38 |
|
|
|
39 |
|
|
#define NAMING_PREFIX "SUBFUNC_PFACT_" |
40 |
|
|
#define SIEVE_SIZE (2310) /* 2 * 3 * 5 * 7 * 11 */ |
41 |
|
|
|
42 |
|
|
unsigned int pfacts[] = {2, 3, 5, 7, 11}; |
43 |
|
|
unsigned int sieve_table_a[SIEVE_SIZE]; |
44 |
|
|
char *output_header[] = |
45 |
|
|
{ |
46 |
|
|
"//This file is an automatically-generated sieve table, generated by the", |
47 |
|
|
"//program \"sieve_gen.c\".", |
48 |
|
|
"//", |
49 |
|
|
NULL |
50 |
|
|
}; |
51 |
|
|
char *output_footer[] = |
52 |
|
|
{ |
53 |
|
|
"//", |
54 |
|
|
"//End of automatically-generated file.", |
55 |
|
|
NULL |
56 |
|
|
}; |
57 |
|
|
|
58 |
|
|
|
59 |
|
|
int main(int argc, char *argv[]) |
60 |
|
|
{ |
61 |
|
|
int i, j; |
62 |
|
|
unsigned p, q; |
63 |
|
|
unsigned current_factor; |
64 |
|
|
char **cptr; |
65 |
|
|
|
66 |
|
|
//Initialize the sieve table. */ |
67 |
|
|
for (i=0; i < SIEVE_SIZE; i++) |
68 |
|
|
{ |
69 |
|
|
sieve_table_a[i] = 1; |
70 |
|
|
} |
71 |
|
|
|
72 |
|
|
/* For each prime component, mark off all multiples. */ |
73 |
|
|
for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++) |
74 |
|
|
{ |
75 |
|
|
current_factor = pfacts[i]; |
76 |
|
|
|
77 |
|
|
p = 0; |
78 |
|
|
while (p < SIEVE_SIZE) |
79 |
|
|
{ |
80 |
|
|
sieve_table_a[p] = 0; |
81 |
|
|
p += current_factor; |
82 |
|
|
} |
83 |
|
|
} |
84 |
|
|
|
85 |
|
|
//Output the header. |
86 |
|
|
cptr = output_header; |
87 |
|
|
while (*cptr) |
88 |
|
|
{ |
89 |
|
|
printf("%s\n", *cptr); |
90 |
|
|
cptr++; |
91 |
|
|
} |
92 |
|
|
|
93 |
|
|
//Convert the table of multiples into a table of differentials. Each non-zero |
94 |
|
|
//entry will be replaced by the distance to the next entry. |
95 |
|
|
for (i=0; i < SIEVE_SIZE; i++) |
96 |
|
|
{ |
97 |
|
|
if (sieve_table_a[i]) |
98 |
|
|
{ |
99 |
|
|
p = (i+1) % SIEVE_SIZE; |
100 |
|
|
while (sieve_table_a[p] == 0) |
101 |
|
|
{ |
102 |
|
|
sieve_table_a[i]++; |
103 |
|
|
p = (p+1) % SIEVE_SIZE; |
104 |
|
|
} |
105 |
|
|
} |
106 |
|
|
} |
107 |
|
|
|
108 |
|
|
//Print out the table of differentials for reference. Each entry will |
109 |
|
|
//be annotated with the prime factors that divide it. |
110 |
|
|
printf("//\n"); |
111 |
|
|
printf("//For reference, below is the uncompressed table of differentials. Each table\n"); |
112 |
|
|
printf("//entry is annotated with the prime factors that divide it, if any.\n"); |
113 |
|
|
printf("//\n"); |
114 |
|
|
for (i=0; i < SIEVE_SIZE; i++) |
115 |
|
|
{ |
116 |
|
|
printf("// sieve_table[%5d]: %3d (", i, sieve_table_a[i]); |
117 |
|
|
q = 0; |
118 |
|
|
for (j=0; j<sizeof(pfacts)/sizeof(pfacts[0]); j++) |
119 |
|
|
{ |
120 |
|
|
if ((i % pfacts[j]) == 0) |
121 |
|
|
{ |
122 |
|
|
printf("[%d]", pfacts[j]); |
123 |
|
|
q = 1; |
124 |
|
|
} |
125 |
|
|
} |
126 |
|
|
if (!q) |
127 |
|
|
printf("NONE"); |
128 |
|
|
printf(")\n"); |
129 |
|
|
} |
130 |
|
|
printf("//\n"); |
131 |
|
|
|
132 |
|
|
//Now we compress the table and output the code proper. |
133 |
|
|
printf("#define %sN_SIEVE_FACTORS (%d)\n", NAMING_PREFIX, sizeof(pfacts)/sizeof(pfacts[0])); |
134 |
|
|
printf("unsigned %ssieve_factors[] = {", NAMING_PREFIX); |
135 |
|
|
for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++) |
136 |
|
|
{ |
137 |
|
|
printf("%d", pfacts[i]); |
138 |
|
|
if (i != (sizeof(pfacts)/sizeof(pfacts[0]) - 1)) |
139 |
|
|
printf(","); |
140 |
|
|
} |
141 |
|
|
|
142 |
|
|
printf("}\n"); |
143 |
|
|
printf("//\n"); |
144 |
|
|
q = 0; |
145 |
|
|
for (i=0; i < SIEVE_SIZE; i++) |
146 |
|
|
if (sieve_table_a[i]) |
147 |
|
|
q++; |
148 |
|
|
printf("#define %sN_SIEVE (%u)\n", NAMING_PREFIX, j); |
149 |
|
|
printf("unsigned %ssieve[] = {\n", NAMING_PREFIX); |
150 |
|
|
j = 0; |
151 |
|
|
for (i=0; i < SIEVE_SIZE; i++) |
152 |
|
|
{ |
153 |
|
|
if (sieve_table_a[i]) |
154 |
|
|
{ |
155 |
|
|
printf(" %3d", sieve_table_a[i]); |
156 |
|
|
if (j==q) |
157 |
|
|
printf(" "); |
158 |
|
|
else |
159 |
|
|
printf(","); |
160 |
|
|
printf(" /* [%5d] (was [%d]) */\n", j, i); |
161 |
|
|
j++; |
162 |
|
|
} |
163 |
|
|
} |
164 |
|
|
printf(" };\n"); |
165 |
|
|
|
166 |
|
|
//Output the footer. |
167 |
|
|
cptr = output_footer; |
168 |
|
|
while (*cptr) |
169 |
|
|
{ |
170 |
|
|
printf("%s\n", *cptr); |
171 |
|
|
cptr++; |
172 |
|
|
} |
173 |
|
|
|
174 |
|
|
return(0); |
175 |
|
|
} |
176 |
|
|
|
177 |
|
|
//****************************************************************************************************** |
178 |
dashley |
175 |
//End of file SIEVE_GEN.C |
179 |
dashley |
172 |
//****************************************************************************************************** |