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