1
2 /*THIS C LANGUAGE SOURCE-CODE FILE CAN BE SUCCESSFULLY COMPILED INTO A
3 WORKING WINDOWS PROGRAM BY BORLAND (Turbo) C++ 4.52, BY BORLAND C++
4 BUILDER 5, BY MICROSOFT VISUAL C++ 6, AND BY OPEN WATCOM 1.2. Other
5 compilers for Windows programs have not been tested. Note that the
6 first of the two Borland compilers dates from the era when Windows
7 started to replace DOS widely, and Borland was starting to drop the
8 word "Turbo" from its application-development tools. The others are
9 thorough-going Windows compilers, suitable even for Windows 2000/XP.
10 Note that Borland no longer supports the (Turbo) C++ 4.52 compiler,
11 but does practically give it away these days (as part of a how-to-
12 learn-C-programming package), so anyone who wants can compile this
13 file most inexpensively.
14
15 The exact steps to compile the program differ with each compiler, but
16 are similar enough to be described as follows: Set up a Project named
17 PRMPRESS, and use the Project Options Editor/Configuration-Tool to
18 delete ALL default files, such as "PRMPRESS.RES" or "PRMPRESS.DEF",
19 and ensure that the ONLY Project file is this one, PRMPRESS.C -- you
20 may have to specify a C Project and not a C++ Project, and if you can
21 specify an EMPTY project do so. Ensuring that this PRMPRESS.C file is
22 the sole source-code file then becomes easy. Note that this file is
23 compatible with pre-1999 ANSI C standards, EXCEPT for lots of usage
24 of pairs of ordinary slash marks // as comment-indicators. (In 1999
25 the double-slash comment indicator became part of the ANSI standard
26 for the C programming language.)
27
28 BEWARE OF THE COMPILER/DEVELOPMENT-ENVIRONMENT REPLACING SPACES WITH
29 TABS!!! THERE ARE NO TABS IN THIS FILE; NEARLY ALL INDENTATIONS HERE
30 ARE PAIRS OF SPACES. The problem of the moment is that different
31 people prefer different tab-sizes, and much careful formatting at one
32 tab-size looks really ugly under almost any other. These compilers
33 mostly offer built-in source-code-editors, along with options that
34 allow you to specify that tabs should not be used at all, and this is
35 recommended. (Exception: The Open Watcom compiler allows you to
36 specify your favorite text editor as part of its Integrated
37 Development Environment -- so that editor's own configuration must be
38 examined to eliminate tabs.)
39
40 After compiling, the executable file PRMPRESS.EXE should successfully
41 work as described elsewhere herein. However, if PRMPRESS.EXE is
42 copied to another computer, where it was not compiled, it may be
43 necessary to copy certain other files that come with the compiler,
44 and to keep them together. The short list:
45 If compiled under Borland (Turbo) C++ 4.52, the file CW3215.DLL is
46 required.
47 If compiled under Borland C++ Builder 5, the number of required
48 support-files can depend on a variety of things, such as whether
49 or not the program was compiled for debugging. You will discover
50 which ones you need as you attempt to run a copy of PRMPRESS.EXE
51 on a computer that contains no compiler. Note that Borland
52 considers those files to be "redistributables" -- they are
53 INTENDED to be copied along with .EXE files.
54 If compiled under Microsoft Visual C++ 6, no other files are
55 required. Since this PRMPRESS program was written for Windows,
56 and since Microsoft is the monopolistic provider of the Windows
57 Operating System, it figures that the Microsoft compiler has a
58 "home team advantage" over competitor compilers.
59 If compiled under Open Watcom 1.2, no other files are required.
60 The requested donation appears to have been earned!
61
62 Note that the PRMPRESS program uses no obscure Windows functions,
63 and so is compatible with "WINE" under Linux. Since this file is
64 being openly shared with the general public, with no restrictions, it
65 is expected that someone will quickly replace the Windows-specific
66 code with Linux-specific code, while hardly touching the program's
67 operational algorithms. Various modifications will be necessary if
68 this program is used with another compiler or Operating System (for
69 example, a lot of backslash \ symbols in Windows file names must
70 edited into regular slash / symbols under Linux or Unix).
71 */
72
73 ////////////////////// SOURCE CODE BEGINS ////////////////////////////
74 // Header files list
75 #include <windows.h>
76 #include <winbase.h>
77 #include <malloc.h>
78 #include <stdlib.h>
79 #include <stdio.h>
80 #include <string.h>
81 #include <ctype.h>
82 #include <io.h>
83
84
85 // Here is an easy way to simplify the various common data types
86 typedef signed char S_08; // signed, 8 bits
87 typedef signed short int S_16; // signed, 16 bits
88 typedef signed long int S_32; // signed, 32 bits
89 typedef unsigned char U_08; // unsigned, 8 bits
90 typedef unsigned short int U_16; // unsigned, 16 bits
91 typedef unsigned long int U_32; // unsigned, 32 bits
92 // NOW THERE IS NO POSSIBLE CONFUSION
93
94
95
96
97 // Error Codes: Out of Memory, Defective Algorithm,
98 // Opening File, File Read, File Write, Bad Data,
99 #define PRM_ERR_OM 1
100 #define PRM_ERR_DA 2
101 #define PRM_ERR_OF 3
102 #define PRM_ERR_FR 4
103 #define PRM_ERR_FW 5
104 #define PRM_ERR_BD 6
105 #define PRM_WM_QUIT 100
106 // That last one is not an error code; indicates user interrupting by
107 // pressing ESC key
108
109
110
111
112
113
114 // Prototypes (also known as "forward declarations") of subroutine
115 // functions in this file
116 LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam,
117 LPARAM lParam);
118 S_16 ProcessMessages(void);
119 S_16 FindPrimes(void);
120
121 // Global Variables.
122 HWND hwnd;
123 FILE *prmfil, *dexfil;
124 HFONT hfont1;
125 HINSTANCE previnst;
126 RECT rect;
127 COLORREF oldcolr;
128 char keynam[] = " "
129 " ",
130 tmpstr[300], ch, prmdrv[2] = " ", dirstr[40];
131 char *cp;
132 U_08 cnds[32768], buf[4096], *lim, *bi, *ci, *c2, *ti, by, bt;
133 S_16 L, ret, task = 0,
134 painting = 0, working = 0;
135 U_16 ttl, *ixp, dex[150000];
136 U_32 prm, prms[13084], todo = 65536, cand, tmp1,
137 *pr, grand, *pri;
138 /* The table below COULD be used to generate Candidate Numbers, which
139 then must be tested for Primality. Just start with ONE, and
140 sequentially add each number in the table, to create a candidate.
141 Thus: 1+16=17; 17+2=19; 19+4=23; 23+6=29; 29+2=31; 31+6=37; 37+4=41;
142 41+2=43; etc. When the end of this table is reached, just return to
143 start of the table and keep on adding. Using this table will prevent
144 ANY Candidate from being divisible by 2, 3, 5, 7, 11, or 13. The
145 trick is basically simple; the product of 2*3*5*7*11*13 is 30030.
146 Take all the numbers from 1 to 30031, and weed out everything
147 divisible by 2, 3, 5, 7, 11, and 13. Of the 5761 numbers that
148 survive, take the difference between every adjacent pair. Those
149 differences constitute this table; if every number in it was added up,
150 the sum would be 30030. Thus this table represents a CYCLE OF
151 NON-DIVISIBILITY by the primes 2, 3, 5, 7, 11, and 13.
152
153 NOTE: Primes 2, 3, 5, 7, 11, and 13 are excluded from the
154 all-encompassing remarks below. In this PRMPRESS program, the table
155 will actually be used to compress 203,280,221 primes (all that can fit
156 in 32 bits, or 4 bytes of data), so that less than 103 million bytes
157 of disk space are needed to hold them. To understand the way it
158 works, recall that the 5760 data-items in the table let us generate
159 values that include ALL primes and SOME composites. If we associate
160 them with bit-flags (Prime or Not-Prime), then every 30030 numbers
161 that are condensed to these 5760 data items (as described in previous
162 paragraph), are condensed further to only 720 bytes (5760 bits). The
163 total compression ratio is about 41.7 to 1, so all primes in the first
164 4,294,967,296 numbers can be squeezed to 102,976,239 bytes.
165
166 This PRMPRESS program will also create an index file. It will consist
167 of two-byte values indicating how many primes exist in each range of
168 30030 numbers. There will be 143,023 entries in this file, so its
169 size will be 286,046 bytes. To be used efficiently, to locate the
170 Nth prime, the whole file should be loaded, and a table of SUMS
171 generated. That table would consist of 143,023 4-byte values (the
172 last entry being 203,280,221). Each adjacent pair of values indicates
173 a RANGE in which N might be found; a binary search of the table will
174 quickly locate the correct range for a specified N; THE LOCATION OF
175 THE RANGE indicates which group of 30030bytes->720bytes inside the
176 main prime file is the place where N can specifically be found. The
177 table below will then be used during the examination of the bits in
178 those 720 bytes, so that the Nth prime can be generated. */
179 U_08 tbl[5761] =
180 {16, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6,
181 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6,
182 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10,
183 6, 6, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 4, 6, 8, 6,
184 10, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 8, 10, 2,
185 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 8, 4, 2, 6, 4,
186 6, 12, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 10, 2, 4,
187 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6,
188 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6,
189 4, 8, 4, 6, 8, 10, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2,
190 10, 2, 4, 2, 4, 14, 4, 2, 4, 6, 6, 2, 6, 4, 8, 10,
191 8, 4, 2, 4, 6, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2,
192 4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2, 6, 4, 8, 6, 4,
193 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 6, 4, 8, 10,
194 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10,
195 12, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 6, 10,
196 6, 8, 4, 2, 4, 2, 4, 8, 6, 12, 4, 6, 2, 12, 4, 2,
197 4, 6, 8, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 10,
198 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8,
199 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 8, 6, 4, 2,
200 10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 6, 4,
201 2, 6, 4, 6, 8, 6, 4, 2, 12, 10, 6, 2, 4, 6, 2, 12,
202 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6,
203 2, 6, 4, 2, 10, 6, 2, 6, 4, 12, 6, 8, 6, 4, 2, 4,
204 8, 6, 4, 6, 2, 4, 6, 8, 6, 6, 4, 6, 2, 6, 4, 2,
205 4, 2, 10, 12, 2, 4, 12, 2, 6, 4, 2, 4, 6, 6, 2, 12,
206 6, 4, 18, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6,
207 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 6, 4, 6, 2,
208 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
209 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2,
210 4, 14, 10, 2, 4, 2, 4, 6, 2, 6, 10, 6, 6, 2, 10, 2,
211 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6,
212 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4,
213 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4,
214 2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 10, 6, 6, 2, 6, 4,
215 2, 4, 2, 10, 2, 12, 4, 6, 6, 2, 12, 4, 6, 6, 2, 6,
216 4, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6,
217 8, 6, 6, 10, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4,
218 8, 6, 4, 2, 4, 6, 6, 8, 4, 8, 4, 6, 8, 4, 2, 4,
219 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6,
220 6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6,
221 14, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 8, 4, 8,
222 6, 10, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2,
223 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 6, 6, 10, 8, 4, 2,
224 4, 6, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 12,
225 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 10, 2, 4, 6, 8,
226 6, 4, 2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4,
227 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 12, 2, 4,
228 2, 4, 6, 2, 6, 4, 2, 16, 2, 6, 4, 2, 10, 6, 8, 4,
229 2, 4, 2, 12, 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6,
230 4, 2, 4, 2, 12, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6,
231 6, 2, 6, 4, 2, 10, 6, 8, 10, 2, 4, 8, 6, 4, 6, 2,
232 4, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 10, 12, 2,
233 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14,
234 6, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4,
235 8, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2,
236 10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4,
237 6, 2, 10, 8, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10,
238 2, 4, 6, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6,
239 12, 2, 4, 6, 8, 6, 10, 2, 4, 8, 6, 6, 4, 2, 4, 6,
240 2, 6, 4, 2, 6, 10, 2, 10, 2, 6, 4, 6, 8, 4, 6, 12,
241 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 14, 4, 6, 2,
242 4, 6, 2, 6, 10, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2,
243 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8,
244 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10,
245 2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4, 8, 6, 4, 2, 4,
246 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6,
247 4, 6, 12, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4, 2, 10,
248 2, 12, 6, 4, 6, 2, 10, 2, 4, 6, 6, 8, 4, 2, 6, 18,
249 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 6, 4, 6,
250 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4,
251 2, 4, 6, 6, 8, 6, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6,
252 4, 12, 6, 2, 6, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 2,
253 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6,
254 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10,
255 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 8,
256 4, 2, 10, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 14, 6,
257 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 10, 2, 4, 2, 10,
258 2, 10, 6, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
259 10, 6, 8, 6, 6, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
260 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2,
261 6, 4, 2, 4, 12, 2, 10, 2, 10, 14, 4, 2, 4, 2, 4, 8,
262 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4,
263 14, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4,
264 2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 10, 2, 6,
265 6, 4, 2, 4, 6, 12, 2, 4, 2, 12, 10, 2, 4, 2, 10, 2,
266 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 4, 6,
267 8, 16, 2, 4, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2, 6,
268 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 16, 2, 6, 4, 8,
269 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 10,
270 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6,
271 2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 6, 4,
272 8, 6, 4, 6, 2, 4, 14, 6, 4, 2, 10, 2, 6, 4, 2, 4,
273 2, 10, 2, 10, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4,
274 8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 6, 6, 2, 6,
275 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 6, 4, 6,
276 2, 6, 6, 4, 6, 6, 12, 2, 6, 10, 8, 4, 2, 4, 2, 4,
277 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 8,
278 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6,
279 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 10, 2,
280 6, 6, 4, 6, 6, 8, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4,
281 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 14, 4, 6, 2,
282 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 10, 6, 2, 6, 10,
283 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 8,
284 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 6, 6,
285 2, 12, 4, 2, 4, 8, 6, 6, 4, 2, 10, 2, 10, 6, 2, 4,
286 6, 2, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 6, 8, 6, 4,
287 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 12, 4, 6, 2, 6, 4,
288 2, 4, 2, 10, 12, 2, 4, 2, 10, 8, 4, 2, 4, 6, 6, 2,
289 10, 2, 6, 18, 4, 2, 4, 6, 8, 6, 4, 6, 2, 4, 6, 2,
290 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 12, 2, 12, 4, 2, 4,
291 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4,
292 2, 6, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2,
293 10, 2, 4, 2, 22, 2, 4, 2, 4, 6, 2, 6, 4, 6, 12, 2,
294 6, 4, 2, 10, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
295 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 6, 12, 10, 2, 4, 2,
296 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 6,
297 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 8,
298 4, 2, 4, 2, 10, 2, 10, 2, 4, 12, 2, 6, 6, 4, 6, 6,
299 2, 6, 4, 2, 6, 4, 6, 8, 6, 6, 4, 8, 10, 6, 2, 4,
300 6, 8, 6, 4, 2, 12, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4,
301 2, 4, 8, 6, 4, 2, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4,
302 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 8, 6, 4, 2, 4, 6,
303 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10, 6, 2, 6, 4, 2,
304 4, 6, 6, 8, 6, 6, 10, 12, 2, 4, 2, 4, 8, 10, 6, 2,
305 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10,
306 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6,
307 8, 4, 2, 4, 2, 4, 14, 4, 8, 4, 6, 2, 6, 6, 4, 2,
308 10, 8, 4, 2, 4, 12, 2, 10, 2, 4, 2, 4, 6, 2, 12, 4,
309 6, 8, 10, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6,
310 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 10, 2, 10,
311 6, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4,
312 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 10, 2, 12, 4, 6,
313 8, 6, 4, 2, 4, 2, 10, 2, 16, 2, 4, 6, 2, 10, 2, 4,
314 6, 6, 2, 6, 4, 2, 10, 14, 6, 4, 2, 4, 8, 6, 4, 6,
315 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10, 12,
316 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 12, 2, 6, 4, 14,
317 4, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4,
318 6, 2, 6, 6, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2,
319 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14,
320 4, 8, 10, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10,
321 2, 4, 2, 4, 6, 8, 4, 6, 6, 6, 2, 6, 4, 2, 6, 10,
322 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2,
323 4, 6, 2, 10, 2, 6, 10, 2, 10, 2, 4, 2, 4, 14, 4, 2,
324 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 6, 4, 8, 6, 4,
325 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2,
326 10, 12, 2, 4, 6, 6, 2, 6, 6, 4, 12, 2, 6, 4, 2, 10,
327 6, 8, 4, 2, 6, 4, 8, 6, 10, 2, 4, 6, 14, 4, 2, 10,
328 2, 6, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 8, 6, 4, 2,
329 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 6, 2, 4, 8, 6,
330 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2,
331 10, 2, 10, 2, 6, 10, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2,
332 6, 10, 8, 6, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4,
333 2, 4, 8, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2,
334 6, 4, 2, 10, 6, 2, 6, 12, 4, 6, 8, 4, 2, 4, 2, 4,
335 8, 6, 4, 8, 4, 6, 8, 6, 4, 2, 4, 6, 8, 4, 2, 4,
336 2, 10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 4, 6, 8, 6, 6,
337 6, 4, 6, 12, 6, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6,
338 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2,
339 6, 4, 12, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2,
340 18, 4, 6, 2, 4, 6, 2, 12, 4, 2, 12, 6, 4, 2, 4, 12,
341 2, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 10,
342 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
343 6, 4, 6, 2, 6, 4, 2, 6, 10, 12, 6, 2, 10, 2, 6, 4,
344 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8,
345 6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4,
346 12, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6, 2, 6, 4,
347 2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6,
348 6, 6, 4, 6, 2, 10, 6, 2, 12, 10, 2, 4, 2, 4, 6, 2,
349 6, 4, 6, 6, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 14,
350 6, 10, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 6, 6, 10,
351 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 14, 6, 4, 2, 6,
352 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10,
353 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6,
354 8, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 10, 8,
355 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 10, 2, 4, 2,
356 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6,
357 4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2,
358 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 6,
359 4, 6, 2, 6, 4, 2, 4, 12, 8, 4, 2, 16, 8, 4, 2, 4,
360 2, 4, 8, 16, 2, 4, 8, 12, 4, 2, 4, 6, 2, 6, 4, 6,
361 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2,
362 6, 6, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6,
363 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2,
364 4, 2, 10, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8,
365 10, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 8, 6,
366 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10,
367 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6,
368 2, 4, 6, 14, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10,
369 6, 6, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 10, 6, 14,
370 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6, 6, 4, 6, 2,
371 6, 4, 2, 4, 2, 10, 12, 2, 6, 10, 2, 6, 4, 6, 6, 6,
372 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 4,
373 6, 2, 6, 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 12, 4,
374 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8,
375 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4,
376 6, 2, 10, 2, 6, 12, 10, 6, 2, 4, 6, 2, 6, 4, 6, 6,
377 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10,
378 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 2, 12,
379 4, 2, 4, 6, 12, 2, 4, 12, 2, 6, 4, 2, 6, 4, 18, 2,
380 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 12, 4, 6, 2,
381 6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6,
382 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 6, 12, 6, 4, 6, 6,
383 6, 8, 6, 4, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4,
384 2, 4, 8, 6, 4, 2, 4, 6, 8, 6, 4, 8, 4, 6, 8, 4,
385 2, 4, 2, 4, 8, 6, 4, 12, 6, 2, 6, 10, 2, 4, 6, 2,
386 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4,
387 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 6, 8, 10, 6, 2,
388 4, 8, 6, 6, 4, 2, 4, 6, 2, 10, 6, 2, 10, 2, 10, 2,
389 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6,
390 8, 4, 2, 6, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2,
391 4, 6, 8, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 6, 2, 10,
392 2, 4, 14, 6, 4, 2, 10, 6, 8, 4, 6, 2, 4, 8, 6, 10,
393 2, 4, 6, 2, 12, 4, 6, 6, 2, 6, 6, 4, 2, 12, 10, 2,
394 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4,
395 6, 8, 4, 6, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2,
396 4, 14, 4, 2, 4, 2, 10, 2, 10, 6, 2, 10, 2, 6, 4, 2,
397 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 10,
398 6, 2, 4, 6, 2, 6, 6, 6, 4, 8, 6, 4, 2, 4, 2, 10,
399 12, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 10, 8, 4, 14,
400 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2,
401 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 6, 6, 2, 6, 4,
402 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 4, 14,
403 4, 6, 2, 12, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12,
404 10, 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6,
405 4, 6, 8, 4, 2, 4, 6, 14, 10, 2, 4, 6, 2, 6, 6, 4,
406 2, 10, 2, 6, 4, 2, 16, 2, 10, 2, 4, 2, 4, 6, 8, 6,
407 4, 12, 2, 10, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4,
408 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 6, 10,
409 2, 10, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6,
410 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 10, 8, 6, 4,
411 12, 2, 6, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4, 8, 10, 2,
412 4, 6, 6, 2, 6, 4, 8, 4, 14, 4, 2, 4, 2, 4, 8, 6,
413 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10,
414 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2,
415 6, 10, 8, 4, 2, 4, 2, 12, 10, 6, 6, 8, 6, 6, 4, 2,
416 4, 6, 2, 6, 10, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6,
417 4, 2, 4, 6, 8, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4,
418 8, 6, 4, 8, 4, 6, 2, 6, 10, 2, 4, 6, 8, 4, 2, 4,
419 2, 10, 2, 10, 2, 4, 2, 4, 6, 12, 2, 4, 6, 8, 6, 4,
420 2, 6, 10, 8, 4, 6, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6,
421 6, 4, 6, 6, 2, 12, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8,
422 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6,
423 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2,
424 4, 2, 10, 12, 6, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6,
425 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 10, 2, 4, 6, 2,
426 12, 6, 4, 6, 2, 6, 4, 2, 4, 2, 22, 2, 4, 2, 10, 2,
427 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 6, 2, 4,
428 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4,
429 2, 4, 12, 2, 12, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2,
430 6, 4, 2, 6, 4, 6, 8, 6, 4, 2, 4, 18, 6, 2, 10, 2,
431 6, 6, 4, 2, 4, 8, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4,
432 6, 2, 6, 4, 12, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4,
433 6, 8, 6, 10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 2, 6, 4,
434 2, 6, 10, 2, 10, 2, 4, 6, 6, 8, 4, 2, 4, 12, 2, 6,
435 6, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8,
436 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10,
437 6, 2, 6, 10, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2,
438 6, 4, 14, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4,
439 2, 4, 12, 2, 10, 2, 4, 2, 4, 8, 6, 6, 4, 6, 6, 2,
440 10, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6,
441 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 8,
442 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4,
443 2, 4, 2, 4, 8, 10, 6, 2, 12, 6, 6, 4, 6, 6, 2, 6,
444 4, 6, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6,
445 2, 6, 6, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4,
446 6, 2, 6, 6, 6, 4, 6, 8, 4, 6, 2, 10, 2, 10, 2, 4,
447 2, 4, 6, 2, 10, 2, 4, 6, 14, 4, 2, 6, 4, 6, 8, 4,
448 6, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6,
449 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10,
450 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 8,
451 4, 6, 2, 16, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6,
452 2, 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 4, 2, 16, 8, 6,
453 4, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2,
454 10, 2, 4, 2, 10, 12, 2, 4, 2, 12, 6, 4, 2, 4, 6, 6,
455 2, 10, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4,
456 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 14, 4,
457 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 8,
458 4, 2, 4, 2, 4, 14, 10, 2, 10, 2, 12, 4, 2, 4, 6, 2,
459 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6,
460 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 6, 6, 8, 6, 10, 2,
461 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10,
462 2, 4, 2, 10, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6,
463 14, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 10, 2, 4, 8,
464 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 10,
465 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6,
466 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2,
467 10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 6, 2, 6, 12, 4, 6,
468 12, 2, 4, 2, 4, 8, 6, 4, 6, 6, 8, 6, 6, 4, 2, 4,
469 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6,
470 4, 6, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 18,
471 6, 2, 4, 8, 6, 6, 4, 2, 10, 2, 6, 4, 6, 12, 2, 10,
472 2, 4, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 12, 6, 4, 6,
473 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4,
474 2, 4, 6, 8, 4, 2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 10,
475 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8,
476 6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2,
477 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 10, 6, 2, 6, 4, 2,
478 6, 4, 14, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12,
479 6, 4, 8, 6, 4, 6, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6,
480 4, 2, 4, 6, 6, 8, 4, 2, 10, 6, 8, 6, 4, 2, 12, 6,
481 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 6, 4, 2, 10,
482 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 8, 10, 2, 6, 4,
483 14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 2,
484 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 8, 4,
485 2, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 6, 14,
486 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2,
487 12, 10, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4, 2,
488 6, 4, 6, 8, 4, 2, 10, 8, 6, 10, 2, 4, 6, 2, 6, 6,
489 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 12, 2, 4, 2, 4, 6,
490 8, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 12, 2, 4, 2, 4,
491 8, 6, 10, 2, 4, 6, 2, 16, 2, 4, 6, 2, 6, 4, 2, 4,
492 2, 12, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4,
493 2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4, 6, 8,
494 6, 4, 2, 10, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 12,
495 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 6, 4, 2,
496 4, 8, 10, 6, 6, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2,
497 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 10, 6, 8,
498 4, 8, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 14, 6,
499 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6,
500 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4,
501 2, 4, 8, 6, 4, 8, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4,
502 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 10, 6, 6, 8, 6,
503 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 4, 6,
504 2, 6, 6, 4, 12, 2, 6, 6, 4, 12, 2, 10, 2, 4, 2, 4,
505 6, 2, 6, 6, 10, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4,
506 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4,
507 2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6,
508 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2,
509 10, 2, 6, 6, 10, 6, 2, 6, 4, 2, 4, 2, 10, 14, 4, 2,
510 10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4,
511 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2,
512 6, 4, 6, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
513 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 18, 4, 6, 12,
514 2, 6, 6, 4, 2, 4, 6, 2, 12, 4, 2, 12, 10, 2, 4, 2,
515 4, 6, 2, 6, 4, 6, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4,
516 2, 4, 6, 8, 6, 12, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6,
517 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12,
518 2, 6, 4, 2, 6, 10, 12, 2, 4, 6, 8, 6, 4, 6, 2, 4,
519 6, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2,
520 4, 6, 8, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
521 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10,
522 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 8, 6, 4, 2,
523 4, 12, 2, 6, 4, 12, 6, 8, 4, 2, 4, 2, 4, 8, 6, 10,
524 6, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 12, 10,
525 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10,
526 8, 4, 6, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4,
527 6, 8, 4, 6, 2, 10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2,
528 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 6, 4, 2, 4, 8, 10,
529 8, 4, 6, 2, 6, 6, 4, 2, 4, 14, 4, 2, 4, 2, 10, 2,
530 10, 2, 4, 2, 4, 6, 2, 10, 2, 10, 8, 6, 4, 8, 4, 6,
531 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 6,
532 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 4,
533 2, 10, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 12, 6, 4,
534 6, 2, 4, 8, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2,
535 10, 8, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 10, 6,
536 8, 6, 4, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 6, 6, 10,
537 2, 6, 4, 2, 4, 12, 12, 2, 4, 2, 10, 2, 6, 6, 4, 6,
538 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6,
539 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 16, 2,
540 0};
541
542 /* BELOW, This QBASIC program was used to generate the above table.
543 BASIC is uniquely suited for quick output of dinky things like
544 that (no compiling).
545 10 DIM a, b, c, d AS INTEGER
546 50 CLS : a = 0: b = 1: OPEN "C:\CANDIFFS.TXT" FOR OUTPUT AS #1
547 90 FOR d = 17 TO 30031 STEP 2
548 IF (((d MOD 3) > 0) AND ((d MOD 5) > 0) AND ((d MOD 7) > 0)) THEN
549 IF (((d MOD 11) > 0) AND ((d MOD 13) > 0)) THEN
550 c = d - b
551 b = d
552 PRINT #1, RIGHT$((" " +RTRIM$((LTRIM$(STR$(c)))) + ", "), 4);
553 IF a MOD 16 = 15 THEN
554 PRINT #1,
555 END IF
556 a = a + 1
557 END IF
558 END IF
559 NEXT d
560 CLOSE #1
561 END
562 */
563 // AFTERWARDS, of course, CANDIFFS.TXT was copied/pasted/edited in
564 // this file. The tail-end zero was added here, to be an
565 // end-of-table marker.
566
567
568 //////////////////////////////////////////////////////////////////////
569 // BEGIN: WinMain is the primary/required starting point of any
570 // Windows program
571 int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
572 LPSTR szCmdLine, int iCmdShow)
573 { static char szAppName[] = "PrmPress";
574 MSG msg;
575 WNDCLASS wndclass;
576
577
578 cp = szCmdLine; // make global; prevent compiler warning
579 previnst = hPrevInstance; // make global; prevent compiler warning
580
581 // Prepare a fixed-width font
582 hfont1 = CreateFont(0, 7, 0, 0, 0, 0, 0, 0, ANSI_CHARSET,
583 OUT_DEFAULT_PRECIS, CLIP_CHARACTER_PRECIS,
584 DEFAULT_QUALITY, (FIXED_PITCH | FF_MODERN),
585 "SimpleFixed"); // NO UNDERLINE
586 /* (Copied from Language Reference)
587 CreateFont
588 (int nHeight, // logical height of font (0=default)
589 int nWidth, // logical average character width
590 // (0=default, using 7)
591 int nEscapement, // angle of escapement (0=default)
592 int nOrientation, // base-line orientation angle(0=default)
593 int fnWeight, // font weight (0=default)
594 DWORD fdwItalic, // italic attribute flag (0=False)
595 DWORD fdwUnderline, // underline attribute flag (0=False)
596 DWORD fdwStrikeOut, // strikeout attribute flag (0=False)
597 DWORD fdwCharSet, // character set identifier, using
598 // ANSI_CHARSET
599 DWORD fdwOutputPrecision,// output precision, using default
600 DWORD fdwClipPrecision, // clipping precision, using SOME
601 DWORD fdwQuality, // output quality, using default
602 DWORD fdwPitchAndFamily, // pitch and family,
603 // using Fixed and no 'serif"
604 LPCTSTR lpszFace); // address of typeface name string
605 */
606
607 // FINALLY READY TO CREATE A WINDOW FOR THIS PROGRAM
608 //wndclass.Size = sizeof(wndclass);
609 wndclass.style = CS_HREDRAW | CS_VREDRAW;
610 wndclass.lpfnWndProc = WndProc;
611 wndclass.cbClsExtra = 0;
612 wndclass.cbWndExtra = 0;
613 wndclass.hInstance = hInstance;
614 wndclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
615 wndclass.hCursor = LoadCursor(NULL, IDC_ARROW);
616 wndclass.hbrBackground = (HBRUSH)GetStockObject(LTGRAY_BRUSH);
617 wndclass.lpszMenuName = NULL;
618 wndclass.lpszClassName = szAppName;
619 //wndclass.hIconSm = LoadIcon(NULL, IDI_APPLICATION); //NOT USED
620 RegisterClass(&wndclass);
621 hwnd = CreateWindow(szAppName, "Prime Compression",
622 WS_CAPTION | WS_VISIBLE,
623 5, 5,
624 575, 130,
625 NULL, NULL, hInstance, NULL);
626 ShowWindow(hwnd, iCmdShow);
627 UpdateWindow(hwnd);
628 // Begin main Windows Program Loop; ends when a message returns zero
629 for(;;)
630 { if(GetMessage(&msg, NULL, 0, 0))
631 { TranslateMessage(&msg);
632 DispatchMessage(&msg);
633 }
634 else
635 break; // GetMessage pulled a WM_QUIT and returned zero; exit!
636 }
637 // BEGIN ORGANIZED EXIT PROCESS
638 // CLEAN UP ALL ALLOCATED MEMORY
639 return(msg.wParam); // PRMPRESS.EXE program terminates here
640 }; // END OF WinMain()
641
642
643
644 //////////////////////////////////////////////////////////////////////
645 // Critical Window Procedure: Windows passes User-Activity messages to
646 // it, for processing
647 LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam,
648 LPARAM lParam)
649 { static HDC hdc;
650 static PAINTSTRUCT ps;
651
652
653 GetClientRect(hwnd, &rect); // Get rectangular screen region upon
654 // which text will be displayed
655 switch(iMsg)
656 {/* case WM_CREATE: // All initializations already done;
657 return(0); // ignore WM_CREATE messages
658 */
659
660
661 ////
662 case WM_CHAR:
663 GetKeyNameText(lParam, keynam, 32);
664 if(!strcmp(keynam, "Esc")) // Quit
665 { PostQuitMessage(0);
666 return(0);
667 }
668 if(!strcmp(keynam, "Space"))
669 L = 1;
670 else
671 L = (S_16)strlen(keynam);
672 if (working == 0) // Other keystrokes ignored when this flag set
673 { ch = (char)toupper((int)wParam);
674 if((L == 1) && (ch >= 'A') && (ch <= 'Z'))
675 if(task == 0)
676 prmdrv[0] = ch;
677 InvalidateRect(hwnd, &rect, 0); // Ensure when flowing,
678 } // the window is updated
679
680 // NOTE: Every WndProc() "case" that is processed is normally
681 // expected to return(0). HOWEVER, in this program we want
682 // keystrokes to immediately lead to window-redraws. SO:
683 // return(0); // FLOW TO WM_PAINT FOR ACCEPTED KEYS
684 // (use the return(0) in WM_PAINT)
685
686 ////
687 case WM_PAINT:
688 if(painting)
689 return(0);
690 painting = 1; // multiple calls here will be rejected
691 hdc = BeginPaint (hwnd, &ps);
692 SetBkColor(hdc, 0x00C0C0C0); // reasonably light gray
693 oldcolr = SetTextColor(hdc, 0x00000000);// black
694 SelectObject(hdc, hfont1); // fixed font
695 SetTextColor(hdc, 0x00008000); // moderately dark green
696 TextOut(hdc, // device context
697 1, 2, // LOGICAL (not pixel) X and Y coordinates
698 "THANK YOU, for choosing this prime-generating tool.",
699 51); // length of above string to display
700 SetTextColor(hdc, oldcolr); // black
701 TextOut(hdc, 1, 30, "Press Letter of Drive able to hold "
702 "200,000,000 primes (100 MegaBytes):", 70);
703 TextOut(hdc, 500, 30, prmdrv, 1);
704 if((task == 0) && (prmdrv[0] != ' '))
705 { tmp1 = GetLogicalDrives();// Bitmap of available drives
706 // 1=A, 2=B, 4=C, 8=D, etc, 0=fail
707 if((tmp1 & (1 << ((S_16)(prmdrv[0] - 'A')))) == 0)
708 { MessageBox(NULL, "That drive is not available", "ERROR",
709 MB_OK | MB_ICONSTOP);
710 prmdrv[0] = ' ';
711 }
712 else
713 { task = 1;
714 working = 1;
715 PostMessage(hwnd, WM_COMMAND, // **** BEGIN TASK! ****
716 123456789, 987654321); // with this indicator
717 } }
718 if(task == 1)
719 { TextOut(hdc, 1, 58,
720 "Total Remaining Blocks of Numbers to Process:", 45);
721 TextOut(hdc, 1, 86,
722 "Program automatically exits when finished, "
723 "or abort with ESC.", 61);
724 task = 2;
725 }
726 if(task >= 2)
727 { sprintf(tmpstr, "%5.5d", todo);
728 TextOut(hdc, 330, 58, tmpstr, 5);
729 }
730 EndPaint(hwnd, &ps);
731 painting = 0;
732 return(0); // END OF WM_PAINT
733
734
735 ////
736 case WM_COMMAND:
737 if((wParam == 123456789) && (lParam == 987654321))
738 { sprintf(dirstr, "%s:\\PRIMES", prmdrv);
739 SetLastError(NO_ERROR);
740 CreateDirectory(dirstr, NULL);
741 ret = (S_16)GetLastError();
742 if ((ret != NO_ERROR) && (ret != ERROR_ALREADY_EXISTS))
743 { sprintf(tmpstr, "QUITTING! Code %d regarding Directory %s",
744 ret, dirstr);
745 MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
746 PostQuitMessage(ret);
747 return(0);
748 }
749 // Prepare work area. Note that all primes smaller than 65536 can be
750 // used to find all primes that fit in 32 bits. There are 6542 primes
751 // smaller than 65536. They will be stored in the prms[] array, each
752 // with a special pointer-value which will be explained later.
753 for (L=0; L<13084; L++)
754 prms[L] = 0; // Erase the primes/pointers storage array
755 ti = tbl + 1; // Initialize pointer to second value in
756 // candidate-increment table
757 bi = buf;
758 by = 1; // Initialize first compressed-byte
759 // to claim that ONE is a prime
760 bt = 2; // Initialize first flag-bit-setter
761 // to be used with first tbl[] entry
762 grand = 1; // set this as a flag for later initialization
763 cand = 17;
764 ttl = 6; // primes 2,3,5,7,11,13 are not found by this sieve
765 ixp = dex; // initialize index-file-buffer pointer
766 ret = 0;
767 if(task == 2)
768 { sprintf(dirstr, "%s:\\PRIMES\\COMPRESS.PRM", prmdrv);
769 prmfil = fopen(dirstr, "wb"); // try to open file as binary
770 if(prmfil == NULL) // failed
771 { sprintf(tmpstr, "QUITTING! Could not create compressed "
772 "Primes File:\n%s", dirstr);
773 MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
774 PostQuitMessage(PRM_ERR_OF); //Opening File error (code 3)
775 return(0);
776 }
777 task = 3;
778 }
779 while ((!ret) && (todo))
780 { if(0 < (ret = FindPrimes()))
781 { PostQuitMessage(ret); // any of several possible errors
782 fclose(prmfil);
783 return(0);
784 } }
785 if((!ret) && (!todo))
786 { *bi++ = by; // Save last (probably unfinished)
787 // byte in output buffer
788 fwrite(buf, 1, (bi - buf), prmfil);
789 fclose(prmfil);
790 *ixp++ = ttl; // Save final count of primes associated
791 // with last table-usage
792 sprintf(dirstr, "%s:\\PRIMES\\CMPRMDEX.QNT", prmdrv);
793 dexfil = fopen(dirstr, "wb"); // try to open file as binary
794 if(dexfil == NULL) // failed
795 { sprintf(tmpstr, "QUITTING! Could not create "
796 "Primes Index File:\n%s", dirstr);
797 MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
798 PostQuitMessage(PRM_ERR_OF);// Opening File error (code 3)
799 return(0);
800 }
801 fwrite(dex, 2, (ixp - dex), dexfil); // Index file begins
802 // with a 64-bit total (1st is zero)
803 fclose(dexfil);
804 PostQuitMessage(0); // PROGRAM FLOW COMPLETED;
805 // BEGIN PROPER END-OF-PROGRAM
806 return(0);
807 }
808 }
809 break; // ignore all other WM_COMMAND messages
810
811
812
813 ////
814
815 case WM_DESTROY: // Clean-up work goes here, before ending
816 // overall prime-generate/compress program
817 PostQuitMessage(0); // Note memory allocations freed at end of
818 // WinMain()
819 return(0); // Always return Zero from any Windows
820 // message processed
821 } // All Windows messages not handled in switch block must be
822 // processed below
823 return(DefWindowProc(hwnd, iMsg, wParam, lParam));
824 }; // END OF WndProc()
825
826
827 /******************** MISC SUBROUTINE FUNCTIONS *********************/
828 S_16 ProcessMessages(void)
829 { static MSG mesg; // Make this multi-byte structure static so doesn't
830 // go on the stack.
831 ret = 0; // Initialize return-value-variable to Everything-is-OK.
832 // Below, seek anything in Windows Message Queue for this program
833 while(!ret && PeekMessage(&mesg, NULL, 0, 0, PM_NOREMOVE))
834 { if(GetMessage(&mesg, NULL, 0, 0)) // PeekMessage() found something
835 { TranslateMessage(&mesg);
836 DispatchMessage(&mesg);
837 }
838 else // GetMessage pulled a WM_QUIT
839 { PostQuitMessage(0); // Must put it back in Messge Queue for
840 // primary loop in WinMain()!
841 ret = 1; // Tell this while() loop AND the calling
842 // function to quit.
843 } } // Otherwise loop til processed all
844 // accumulated Messages in the Queue
845 return(ret); // Return-value ret will be 0 when no
846 // messages (remaining) in Queue
847 };
848
849
850 // Each call to this function seeks primes that fall within a range of
851 // 65536 numbers. The goal of this PRMPRESS program is to find all
852 // primes that fit in 32 bits; there will be 65536 calls to this
853 // function. Each found group will be compressed/appended to a single
854 // long file. (Below, most variables having names ending in i are
855 // used for indexing into arrays.)
856 S_16 FindPrimes(void)
857 { for(L=32767, ci=cnds; L>=0; L--) // We will only process the 32768
858 // ODD numbers in each block of 65536
859 *ci++ = (U_08)1; // Initialize candidate buffer to all ONEs,
860 // which will be simple prime/not-prime flags
861 lim = cnds + 32768; // set a Limit of end of candidate-testing area
862 if(todo == 65536) // If this is first call to this function, we want
863 // to fill up the prms[] array with the values
864 // needed to find all the primes in all the OTHER
865 // 65535 blocks.
866 { pri = prms; // Initialize pointer to array of primes and pointers
867 *pri++ = 2; // Set first prime in array; skip to slot for pointer
868 // (then skip that at start of for-loop below)
869 for(pri++,ci=cnds+1; ci<lim; )// Point at second candidate-flag
870 // (represents 3).
871 if(*ci++) // If prime/not-prime flag indicates a prime
872 { *pri++ = (prm = ((ci - cnds)<<1) - 1); // compute/save the
873 // actual prime. That is, take difference between
874 // pointers-to-current-byte in the cnds[] array, and
875 // the start of that array, to get Nth odd number --
876 // then double via bit-shift and reduce by 1 to get
877 // the actual odd number. (Reduce, yes! Because
878 // variable ci has is now pointing at NEXT number.)
879 for(c2=cnds+((prm * prm)>>1); c2<lim; c2+=prm)// first compute
880 // location of square of current prime as starting point
881 // (note bit-shift halving since only odd numbers in array);
882 // then check to see if it is past work-area limit; as long
883 // as loop continues, skip through the work-area at intervals
884 // equal to the current prime.
885 *c2 = 0; //flag this location in work-area as a not-prime
886 *pri++ = (U_32)c2; // SAVE CANDIDATE-POINTER AFTER LOOP ENDS
887 // This is a key to efficiency. In the prms[] array, each
888 // prime will be associated with such a pointer. It IS the
889 // place where, if the cnds[] array was larger, the next odd
890 // number divisible by this prime would be indicated. All we
891 // have to do is subtract the size of the cnds[] array, and
892 // this value becomes the starting point in the next block
893 // of 32768 odd numbers, for more flagging-as-not-prime.
894 // Note that when the pointer to the square of a prime is too
895 // big for any immediate flagging, successive subtractions as
896 // this function is called will quickly bring its value down
897 // to where it WILL work correctly.
898 } }// End of processing of all primes smaller than 65536.
899 else // All of the other 65535 other calls to this function
900 // (with all 32768 candidate flags initialized to ONE)
901 { for(L=1, pri=prms+2; L<6542; L++) // For every prime smaller than
902 // 65536, except for the first (2)
903 { prm = *pri++; // fetch the prime
904 for(ci=(U_08 *)(*pri-32768); ci<lim; ci+=prm)
905 // Fetch/adjust pointer associated with current prime; test for
906 // beyond-end-of-cnds[]-array; during loop adjust pointer for
907 *ci = 0; // flagging candidate as composite
908 *pri++ = (U_32)ci; // Save new pointer value and prepare to
909 // repeat for next prime in prms[] array
910 } }
911 // Now to compress the data among the current array of 32768
912 // candidate-flag-bytes. Note this compression scheme is only for
913 // primes larger than 13. So, previously, variable 'grand' (below)
914 // was initialized to ONE. That means, on the very first call to
915 // this function, it is not greater than 13 in following test. Thus
916 // we can reinitialize grand to 17, the first prime that will be put
917 // into the compressed-data file, and we can set L to indicate that
918 // we want to skip the bytes in the cnds[] array that represent the
919 // odd numbers 1, 3, 5, 7, 9, 11, 13, and 15. On all other calls to
920 // this function, grand will be greater than 13, so it will be left
921 // alone while L is set to Zero, because we want to be able to check
922 // any of the odd numbers that are flagged in the cnds[] array.
923 L = (grand > 13) ? (S_16)0 : (grand=17,(S_16)8);
924 lim = buf + 4096; // reset Limit variable to end of output buffer
925 for(ci=cnds+L; L>=0; L++, grand+=2, ci++) // Set candidate-index to
926 // correct starting place in cnds[] array; test for L changing
927 // from +32767 to -32768 at end of loop; while loop continues,
928 // adjust grand for next odd number and bump index to next flag.
929 // Below, recall 'cand' was initialized to 17. It will be bumped
930 // by values taken from the cycle-of-non-divisibility table.
931 { if(grand == cand)// ONLY when this happens MIGHT we have a prime
932 // among the flag-bytes of the cnds[] array
933 { if(*ci) // current candidate-flag-byte indicates a prime
934 { by |= bt; // Set a bit in compressed-data byte; each byte
935 // represents 8 odd numbers DERIVED FROM THE NON-
936 // DIVISIBILITY TABLE, and only the actual primes
937 // are flagged with ONE-bits.
938 ttl++; // count total number of primes in current block
939 // of 30030 numbers, for the Index File
940 }
941 if(bt == 128) // check for last possible bit-value that fits
942 // in one byte
943 { bt = 1; // reset bit-setter to first bit for next byte
944 *bi++ = by; // save current byte in output buffer
945 if(bi == lim)// Test for end of buffer
946 { fwrite(buf, 1, 4096, prmfil); // save buffer to file
947 bi = buf; // reset buffer index pointer
948 }
949 by = 0; // reset compressed-data byte for next 8 numbers
950 }
951 else // as long as we haven't used highest bit-value
952 bt <<= 1; // double for next bit-that-might-be-set
953 cand += *ti++; // set next candidate that grand must match,
954 // by adding a non-divisibility-table value
955 if(!*ti) // reached end of candidate-increment table?
956 { ti=tbl; // reset to start of table
957 *ixp++ = ttl;// Save current count of primes (in the just-
958 // compressed block of 30030 numbers) to the
959 // index-file buffer.
960 ttl = 0; // reset counter for next Indexed batch of primes
961 } } }
962 todo--;
963 InvalidateRect(hwnd, &rect, 0); // make window update-able
964 ret = ProcessMessages();
965 return(ret);
966 };
|
