Articles   Members Online:
-Article/Tip Search
-News Group Search over 21 Million news group articles.
-Delphi/Pascal
-CBuilder/C++
-C#Builder/C#
-JBuilder/Java
-Kylix
Member Area
-Home
-Account Center
-Top 10 NEW!!
-Submit Article/Tip
-Forums Upgraded!!
-My Articles
-Edit Information
-Login/Logout
-Become a Member
-Why sign up!
-Newsletter
-Chat Online!
-Indexes NEW!!
Employment
-Build your resume
-Find a job
-Post a job
-Resume Search
Contacts
-Contacts
-Feedbacks
-Link to us
-Privacy/Disclaimer
Embarcadero
Visit Embarcadero
Embarcadero Community
JEDI
Links
How to extract info from the middle of one particular compressed file Turn on/off line numbers in source code. Switch to Orginial background IDE or DSP color Comment or reply to this aritlce/tip for discussion. Bookmark this article to my favorite article(s). Print this article
Fetches Nth prime from a 40:1 compressed datafile 19-Oct-04
Category
Algorithm
Language
CBuilder All Versions
Views
427
User Rating
No Votes
# Votes
0
Replies
0
Publisher:
Nemitz, Vernon
Reference URL:
			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 };};


			
Vote: How useful do you find this Article/Tip?
Bad Excellent
1 2 3 4 5 6 7 8 9 10

 

Advertisement
Share this page
Advertisement
Download from Google

Copyright © Mendozi Enterprises LLC