|
Creating a file representing more than 203 million Prime Numbers
by Vernon Nemitz
/*
THIS C LANGUAGE SOURCE-CODE FILE CAN BE SUCCESSFULLY COMPILED INTO A
WORKING WINDOWS PROGRAM BY BORLAND (Turbo) C++ 4.52, BY BORLAND C++
BUILDER 5, BY MICROSOFT VISUAL C++ 6, AND BY OPEN WATCOM 1.2. Other
compilers for Windows programs have not been tested. Note that the
first of the two Borland compilers dates from the era when Windows
started to replace DOS widely, and Borland was starting to drop the
word "Turbo" from its application-development tools. The others are
thorough-going Windows compilers, suitable even for Windows 2000/XP.
Note that Borland no longer supports the (Turbo) C++ 4.52 compiler,
but does practically give it away these days (as part of a how-to-
learn-C-programming package), so anyone who wants can compile this
file most inexpensively.
The exact steps to compile the program differ with each compiler, but
are similar enough to be described as follows: Set up a Project named
PRMPRESS, and use the Project Options Editor/Configuration-Tool to
delete ALL default files, such as "PRMPRESS.RES" or "PRMPRESS.DEF",
and ensure that the ONLY Project file is this one, PRMPRESS.C -- you
may have to specify a C Project and not a C++ Project, and if you can
specify an EMPTY project do so. Ensuring that this PRMPRESS.C file is
the sole source-code file then becomes easy. Note that this file is
compatible with pre-1999 ANSI C standards, EXCEPT for lots of usage
of pairs of ordinary slash marks // as comment-indicators. (In 1999
the double-slash comment indicator became part of the ANSI standard
for the C programming language.)
BEWARE OF THE COMPILER/DEVELOPMENT-ENVIRONMENT REPLACING SPACES WITH
TABS!!! THERE ARE NO TABS IN THIS FILE; NEARLY ALL INDENTATIONS HERE
ARE PAIRS OF SPACES. The problem of the moment is that different
people prefer different tab-sizes, and much careful formatting at one
tab-size looks really ugly under almost any other. These compilers
mostly offer built-in source-code-editors, along with options that
allow you to specify that tabs should not be used at all, and this is
recommended. (Exception: The Open Watcom compiler allows you to
specify your favorite text editor as part of its Integrated
Development Environment -- so that editor's own configuration must be
examined to eliminate tabs.)
After compiling, the executable file PRMPRESS.EXE should successfully
work as described elsewhere herein. However, if PRMPRESS.EXE is
copied to another computer, where it was not compiled, it may be
necessary to copy certain other files that come with the compiler,
and to keep them together. The short list:
If compiled under Borland (Turbo) C++ 4.52, the file CW3215.DLL is
required.
If compiled under Borland C++ Builder 5, the number of required
support-files can depend on a variety of things, such as whether
or not the program was compiled for debugging. You will discover
which ones you need as you attempt to run a copy of PRMPRESS.EXE
on a computer that contains no compiler. Note that Borland
considers those files to be "redistributables" -- they are
INTENDED to be copied along with .EXE files.
If compiled under Microsoft Visual C++ 6, no other files are
required. Since this PRMPRESS program was written for Windows,
and since Microsoft is the monopolistic provider of the Windows
Operating System, it figures that the Microsoft compiler has a
"home team advantage" over competitor compilers.
If compiled under Open Watcom 1.2, no other files are required.
The requested donation appears to have been earned!
Note that the PRMPRESS program uses no obscure Windows functions,
and so is compatible with "WINE" under Linux. Since this file is
being openly shared with the general public, with no restrictions, it
is expected that someone will quickly replace the Windows-specific
code with Linux-specific code, while hardly touching the program's
operational algorithms. Various modifications will be necessary if
this program is used with another compiler or Operating System (for
example, a lot of backslash \ symbols in Windows file names must
edited into regular slash / symbols under Linux or Unix).
*/
////////////////////// SOURCE CODE BEGINS ////////////////////////////
// Header files list
#include <windows.h>
#include <winbase.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <io.h>
// Here is an easy way to simplify the various common data types
typedef signed char S_08; // signed, 8 bits
typedef signed short int S_16; // signed, 16 bits
typedef signed long int S_32; // signed, 32 bits
typedef unsigned char U_08; // unsigned, 8 bits
typedef unsigned short int U_16; // unsigned, 16 bits
typedef unsigned long int U_32; // unsigned, 32 bits
// NOW THERE IS NO POSSIBLE CONFUSION
// Error Codes: Out of Memory, Defective Algorithm,
// Opening File, File Read, File Write, Bad Data,
#define PRM_ERR_OM 1
#define PRM_ERR_DA 2
#define PRM_ERR_OF 3
#define PRM_ERR_FR 4
#define PRM_ERR_FW 5
#define PRM_ERR_BD 6
#define PRM_WM_QUIT 100
// That last one is not an error code; indicates user interrupting by
// pressing ESC key
// Prototypes (also known as "forward declarations") of subroutine
// functions in this file
LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam,
LPARAM lParam);
S_16 ProcessMessages(void);
S_16 FindPrimes(void);
// Global Variables.
HWND hwnd;
FILE *prmfil, *dexfil;
HFONT hfont1;
HINSTANCE previnst;
RECT rect;
COLORREF oldcolr;
char keynam[] = " "
" ",
tmpstr[300], ch, prmdrv[2] = " ", dirstr[40];
char *cp;
U_08 cnds[32768], buf[4096], *lim, *bi, *ci, *c2, *ti, by, bt;
S_16 L, ret, task = 0,
painting = 0, working = 0;
U_16 ttl, *ixp, dex[150000];
U_32 prm, prms[13084], todo = 65536, cand, tmp1,
*pr, grand, *pri;
/* The table below COULD be used to generate Candidate Numbers, which
then must be tested for Primality. Just start with ONE, and
sequentially add each number in the table, to create a candidate.
Thus: 1+16=17; 17+2=19; 19+4=23; 23+6=29; 29+2=31; 31+6=37; 37+4=41;
41+2=43; etc. When the end of this table is reached, just return to
start of the table and keep on adding. Using this table will prevent
ANY Candidate from being divisible by 2, 3, 5, 7, 11, or 13. The
trick is basically simple; the product of 2*3*5*7*11*13 is 30030.
Take all the numbers from 1 to 30031, and weed out everything
divisible by 2, 3, 5, 7, 11, and 13. Of the 5761 numbers that
survive, take the difference between every adjacent pair. Those
differences constitute this table; if every number in it was added up,
the sum would be 30030. Thus this table represents a CYCLE OF
NON-DIVISIBILITY by the primes 2, 3, 5, 7, 11, and 13.
NOTE: Primes 2, 3, 5, 7, 11, and 13 are excluded from the
all-encompassing remarks below. In this PRMPRESS program, the table
will actually be used to compress 203,280,221 primes (all that can fit
in 32 bits, or 4 bytes of data), so that less than 103 million bytes
of disk space are needed to hold them. To understand the way it
works, recall that the 5760 data-items in the table let us generate
values that include ALL primes and SOME composites. If we associate
them with bit-flags (Prime or Not-Prime), then every 30030 numbers
that are condensed to these 5760 data items (as described in previous
paragraph), are condensed further to only 720 bytes (5760 bits). The
total compression ratio is about 41.7 to 1, so all primes in the first
4,294,967,296 numbers can be squeezed to 102,976,239 bytes.
This PRMPRESS program will also create an index file. It will consist
of two-byte values indicating how many primes exist in each range of
30030 numbers. There will be 143,023 entries in this file, so its
size will be 286,046 bytes. To be used efficiently, to locate the
Nth prime, the whole file should be loaded, and a table of SUMS
generated. That table would consist of 143,023 4-byte values (the
last entry being 203,280,221). Each adjacent pair of values indicates
a RANGE in which N might be found; a binary search of the table will
quickly locate the correct range for a specified N; THE LOCATION OF
THE RANGE indicates which group of 30030bytes->720bytes inside the
main prime file is the place where N can specifically be found. The
table below will then be used during the examination of the bits in
those 720 bytes, so that the Nth prime can be generated. */
U_08 tbl[5761] =
{16, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6,
4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6,
4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10,
6, 6, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 4, 6, 8, 6,
10, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 8, 10, 2,
10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 8, 4, 2, 6, 4,
6, 12, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 10, 2, 4,
6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6,
4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6,
4, 8, 4, 6, 8, 10, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2,
10, 2, 4, 2, 4, 14, 4, 2, 4, 6, 6, 2, 6, 4, 8, 10,
8, 4, 2, 4, 6, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2,
4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2, 6, 4, 8, 6, 4,
2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 6, 4, 8, 10,
6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10,
12, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 6, 10,
6, 8, 4, 2, 4, 2, 4, 8, 6, 12, 4, 6, 2, 12, 4, 2,
4, 6, 8, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 10,
2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8,
6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 8, 6, 4, 2,
10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 6, 4,
2, 6, 4, 6, 8, 6, 4, 2, 12, 10, 6, 2, 4, 6, 2, 12,
4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6,
2, 6, 4, 2, 10, 6, 2, 6, 4, 12, 6, 8, 6, 4, 2, 4,
8, 6, 4, 6, 2, 4, 6, 8, 6, 6, 4, 6, 2, 6, 4, 2,
4, 2, 10, 12, 2, 4, 12, 2, 6, 4, 2, 4, 6, 6, 2, 12,
6, 4, 18, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6,
4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 6, 4, 6, 2,
6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2,
4, 14, 10, 2, 4, 2, 4, 6, 2, 6, 10, 6, 6, 2, 10, 2,
6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6,
6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4,
6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4,
2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 10, 6, 6, 2, 6, 4,
2, 4, 2, 10, 2, 12, 4, 6, 6, 2, 12, 4, 6, 6, 2, 6,
4, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6,
8, 6, 6, 10, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4,
8, 6, 4, 2, 4, 6, 6, 8, 4, 8, 4, 6, 8, 4, 2, 4,
2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6,
6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6,
14, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 8, 4, 8,
6, 10, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2,
4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 6, 6, 10, 8, 4, 2,
4, 6, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 12,
2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 10, 2, 4, 6, 8,
6, 4, 2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4,
6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 12, 2, 4,
2, 4, 6, 2, 6, 4, 2, 16, 2, 6, 4, 2, 10, 6, 8, 4,
2, 4, 2, 12, 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6,
4, 2, 4, 2, 12, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6,
6, 2, 6, 4, 2, 10, 6, 8, 10, 2, 4, 8, 6, 4, 6, 2,
4, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 10, 12, 2,
4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14,
6, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4,
8, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2,
10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4,
6, 2, 10, 8, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10,
2, 4, 6, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6,
12, 2, 4, 6, 8, 6, 10, 2, 4, 8, 6, 6, 4, 2, 4, 6,
2, 6, 4, 2, 6, 10, 2, 10, 2, 6, 4, 6, 8, 4, 6, 12,
2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 14, 4, 6, 2,
4, 6, 2, 6, 10, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2,
4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8,
4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10,
2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4, 8, 6, 4, 2, 4,
6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6,
4, 6, 12, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4, 2, 10,
2, 12, 6, 4, 6, 2, 10, 2, 4, 6, 6, 8, 4, 2, 6, 18,
4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 6, 4, 6,
2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4,
2, 4, 6, 6, 8, 6, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6,
4, 12, 6, 2, 6, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 2,
10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6,
4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10,
6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 8,
4, 2, 10, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 14, 6,
4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 10, 2, 4, 2, 10,
2, 10, 6, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
10, 6, 8, 6, 6, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2,
6, 4, 2, 4, 12, 2, 10, 2, 10, 14, 4, 2, 4, 2, 4, 8,
6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4,
14, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4,
2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 10, 2, 6,
6, 4, 2, 4, 6, 12, 2, 4, 2, 12, 10, 2, 4, 2, 10, 2,
6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 4, 6,
8, 16, 2, 4, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2, 6,
10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 16, 2, 6, 4, 8,
4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 10,
2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6,
2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 6, 4,
8, 6, 4, 6, 2, 4, 14, 6, 4, 2, 10, 2, 6, 4, 2, 4,
2, 10, 2, 10, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4,
8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 6, 6, 2, 6,
6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 6, 4, 6,
2, 6, 6, 4, 6, 6, 12, 2, 6, 10, 8, 4, 2, 4, 2, 4,
8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 8,
10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6,
6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 10, 2,
6, 6, 4, 6, 6, 8, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4,
6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 14, 4, 6, 2,
4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 10, 6, 2, 6, 10,
2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 8,
4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 6, 6,
2, 12, 4, 2, 4, 8, 6, 6, 4, 2, 10, 2, 10, 6, 2, 4,
6, 2, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 6, 8, 6, 4,
2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 12, 4, 6, 2, 6, 4,
2, 4, 2, 10, 12, 2, 4, 2, 10, 8, 4, 2, 4, 6, 6, 2,
10, 2, 6, 18, 4, 2, 4, 6, 8, 6, 4, 6, 2, 4, 6, 2,
6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 12, 2, 12, 4, 2, 4,
8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4,
2, 6, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2,
10, 2, 4, 2, 22, 2, 4, 2, 4, 6, 2, 6, 4, 6, 12, 2,
6, 4, 2, 10, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 6, 12, 10, 2, 4, 2,
4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 6,
2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 8,
4, 2, 4, 2, 10, 2, 10, 2, 4, 12, 2, 6, 6, 4, 6, 6,
2, 6, 4, 2, 6, 4, 6, 8, 6, 6, 4, 8, 10, 6, 2, 4,
6, 8, 6, 4, 2, 12, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4,
2, 4, 8, 6, 4, 2, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4,
2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 8, 6, 4, 2, 4, 6,
2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10, 6, 2, 6, 4, 2,
4, 6, 6, 8, 6, 6, 10, 12, 2, 4, 2, 4, 8, 10, 6, 2,
4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10,
2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6,
8, 4, 2, 4, 2, 4, 14, 4, 8, 4, 6, 2, 6, 6, 4, 2,
10, 8, 4, 2, 4, 12, 2, 10, 2, 4, 2, 4, 6, 2, 12, 4,
6, 8, 10, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6,
2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 10, 2, 10,
6, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4,
6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 10, 2, 12, 4, 6,
8, 6, 4, 2, 4, 2, 10, 2, 16, 2, 4, 6, 2, 10, 2, 4,
6, 6, 2, 6, 4, 2, 10, 14, 6, 4, 2, 4, 8, 6, 4, 6,
2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10, 12,
2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 12, 2, 6, 4, 14,
4, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4,
6, 2, 6, 6, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2,
4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14,
4, 8, 10, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10,
2, 4, 2, 4, 6, 8, 4, 6, 6, 6, 2, 6, 4, 2, 6, 10,
8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2,
4, 6, 2, 10, 2, 6, 10, 2, 10, 2, 4, 2, 4, 14, 4, 2,
4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 6, 4, 8, 6, 4,
6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2,
10, 12, 2, 4, 6, 6, 2, 6, 6, 4, 12, 2, 6, 4, 2, 10,
6, 8, 4, 2, 6, 4, 8, 6, 10, 2, 4, 6, 14, 4, 2, 10,
2, 6, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 8, 6, 4, 2,
4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 6, 2, 4, 8, 6,
4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2,
10, 2, 10, 2, 6, 10, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2,
6, 10, 8, 6, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4,
2, 4, 8, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2,
6, 4, 2, 10, 6, 2, 6, 12, 4, 6, 8, 4, 2, 4, 2, 4,
8, 6, 4, 8, 4, 6, 8, 6, 4, 2, 4, 6, 8, 4, 2, 4,
2, 10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 4, 6, 8, 6, 6,
6, 4, 6, 12, 6, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6,
4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2,
6, 4, 12, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2,
18, 4, 6, 2, 4, 6, 2, 12, 4, 2, 12, 6, 4, 2, 4, 12,
2, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 10,
6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
6, 4, 6, 2, 6, 4, 2, 6, 10, 12, 6, 2, 10, 2, 6, 4,
2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8,
6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4,
12, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6, 2, 6, 4,
2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6,
6, 6, 4, 6, 2, 10, 6, 2, 12, 10, 2, 4, 2, 4, 6, 2,
6, 4, 6, 6, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 14,
6, 10, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 6, 6, 10,
2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 14, 6, 4, 2, 6,
4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10,
2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6,
8, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 10, 8,
6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 10, 2, 4, 2,
10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6,
4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2,
6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 6,
4, 6, 2, 6, 4, 2, 4, 12, 8, 4, 2, 16, 8, 4, 2, 4,
2, 4, 8, 16, 2, 4, 8, 12, 4, 2, 4, 6, 2, 6, 4, 6,
2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2,
6, 6, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6,
2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2,
4, 2, 10, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8,
10, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 8, 6,
6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10,
6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6,
2, 4, 6, 14, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10,
6, 6, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 10, 6, 14,
4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6, 6, 4, 6, 2,
6, 4, 2, 4, 2, 10, 12, 2, 6, 10, 2, 6, 4, 6, 6, 6,
2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 4,
6, 2, 6, 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 12, 4,
2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8,
4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4,
6, 2, 10, 2, 6, 12, 10, 6, 2, 4, 6, 2, 6, 4, 6, 6,
6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10,
2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 2, 12,
4, 2, 4, 6, 12, 2, 4, 12, 2, 6, 4, 2, 6, 4, 18, 2,
4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 12, 4, 6, 2,
6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6,
6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 6, 12, 6, 4, 6, 6,
6, 8, 6, 4, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4,
2, 4, 8, 6, 4, 2, 4, 6, 8, 6, 4, 8, 4, 6, 8, 4,
2, 4, 2, 4, 8, 6, 4, 12, 6, 2, 6, 10, 2, 4, 6, 2,
6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4,
6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 6, 8, 10, 6, 2,
4, 8, 6, 6, 4, 2, 4, 6, 2, 10, 6, 2, 10, 2, 10, 2,
4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6,
8, 4, 2, 6, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2,
4, 6, 8, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 6, 2, 10,
2, 4, 14, 6, 4, 2, 10, 6, 8, 4, 6, 2, 4, 8, 6, 10,
2, 4, 6, 2, 12, 4, 6, 6, 2, 6, 6, 4, 2, 12, 10, 2,
4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4,
6, 8, 4, 6, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2,
4, 14, 4, 2, 4, 2, 10, 2, 10, 6, 2, 10, 2, 6, 4, 2,
4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 10,
6, 2, 4, 6, 2, 6, 6, 6, 4, 8, 6, 4, 2, 4, 2, 10,
12, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 10, 8, 4, 14,
4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2,
4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 6, 6, 2, 6, 4,
2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 4, 14,
4, 6, 2, 12, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12,
10, 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6,
4, 6, 8, 4, 2, 4, 6, 14, 10, 2, 4, 6, 2, 6, 6, 4,
2, 10, 2, 6, 4, 2, 16, 2, 10, 2, 4, 2, 4, 6, 8, 6,
4, 12, 2, 10, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4,
6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 6, 10,
2, 10, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6,
4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 10, 8, 6, 4,
12, 2, 6, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4, 8, 10, 2,
4, 6, 6, 2, 6, 4, 8, 4, 14, 4, 2, 4, 2, 4, 8, 6,
4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10,
2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2,
6, 10, 8, 4, 2, 4, 2, 12, 10, 6, 6, 8, 6, 6, 4, 2,
4, 6, 2, 6, 10, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6,
4, 2, 4, 6, 8, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4,
8, 6, 4, 8, 4, 6, 2, 6, 10, 2, 4, 6, 8, 4, 2, 4,
2, 10, 2, 10, 2, 4, 2, 4, 6, 12, 2, 4, 6, 8, 6, 4,
2, 6, 10, 8, 4, 6, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6,
6, 4, 6, 6, 2, 12, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8,
6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6,
12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2,
4, 2, 10, 12, 6, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6,
4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 10, 2, 4, 6, 2,
12, 6, 4, 6, 2, 6, 4, 2, 4, 2, 22, 2, 4, 2, 10, 2,
6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 6, 2, 4,
8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4,
2, 4, 12, 2, 12, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2,
6, 4, 2, 6, 4, 6, 8, 6, 4, 2, 4, 18, 6, 2, 10, 2,
6, 6, 4, 2, 4, 8, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4,
6, 2, 6, 4, 12, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4,
6, 8, 6, 10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 2, 6, 4,
2, 6, 10, 2, 10, 2, 4, 6, 6, 8, 4, 2, 4, 12, 2, 6,
6, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8,
6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10,
6, 2, 6, 10, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2,
6, 4, 14, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4,
2, 4, 12, 2, 10, 2, 4, 2, 4, 8, 6, 6, 4, 6, 6, 2,
10, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6,
2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 8,
4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4,
2, 4, 2, 4, 8, 10, 6, 2, 12, 6, 6, 4, 6, 6, 2, 6,
4, 6, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6,
2, 6, 6, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4,
6, 2, 6, 6, 6, 4, 6, 8, 4, 6, 2, 10, 2, 10, 2, 4,
2, 4, 6, 2, 10, 2, 4, 6, 14, 4, 2, 6, 4, 6, 8, 4,
6, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6,
6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10,
8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 8,
4, 6, 2, 16, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6,
2, 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 4, 2, 16, 8, 6,
4, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2,
10, 2, 4, 2, 10, 12, 2, 4, 2, 12, 6, 4, 2, 4, 6, 6,
2, 10, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4,
6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 14, 4,
2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 8,
4, 2, 4, 2, 4, 14, 10, 2, 10, 2, 12, 4, 2, 4, 6, 2,
10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6,
6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 6, 6, 8, 6, 10, 2,
4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10,
2, 4, 2, 10, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6,
14, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 10, 2, 4, 8,
6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 10,
6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6,
2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2,
10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 6, 2, 6, 12, 4, 6,
12, 2, 4, 2, 4, 8, 6, 4, 6, 6, 8, 6, 6, 4, 2, 4,
6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6,
4, 6, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 18,
6, 2, 4, 8, 6, 6, 4, 2, 10, 2, 6, 4, 6, 12, 2, 10,
2, 4, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 12, 6, 4, 6,
8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4,
2, 4, 6, 8, 4, 2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 10,
2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8,
6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2,
10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 10, 6, 2, 6, 4, 2,
6, 4, 14, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12,
6, 4, 8, 6, 4, 6, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6,
4, 2, 4, 6, 6, 8, 4, 2, 10, 6, 8, 6, 4, 2, 12, 6,
4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 6, 4, 2, 10,
12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 8, 10, 2, 6, 4,
14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 2,
4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 8, 4,
2, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 6, 14,
4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2,
12, 10, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4, 2,
6, 4, 6, 8, 4, 2, 10, 8, 6, 10, 2, 4, 6, 2, 6, 6,
4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 12, 2, 4, 2, 4, 6,
8, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 12, 2, 4, 2, 4,
8, 6, 10, 2, 4, 6, 2, 16, 2, 4, 6, 2, 6, 4, 2, 4,
2, 12, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4,
2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4, 6, 8,
6, 4, 2, 10, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 12,
6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 6, 4, 2,
4, 8, 10, 6, 6, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2,
4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 10, 6, 8,
4, 8, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 14, 6,
4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6,
2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4,
2, 4, 8, 6, 4, 8, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4,
2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 10, 6, 6, 8, 6,
4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 4, 6,
2, 6, 6, 4, 12, 2, 6, 6, 4, 12, 2, 10, 2, 4, 2, 4,
6, 2, 6, 6, 10, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4,
2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4,
2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6,
2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2,
10, 2, 6, 6, 10, 6, 2, 6, 4, 2, 4, 2, 10, 14, 4, 2,
10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4,
2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2,
6, 4, 6, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 18, 4, 6, 12,
2, 6, 6, 4, 2, 4, 6, 2, 12, 4, 2, 12, 10, 2, 4, 2,
4, 6, 2, 6, 4, 6, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4,
2, 4, 6, 8, 6, 12, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6,
4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12,
2, 6, 4, 2, 6, 10, 12, 2, 4, 6, 8, 6, 4, 6, 2, 4,
6, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2,
4, 6, 8, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10,
2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 8, 6, 4, 2,
4, 12, 2, 6, 4, 12, 6, 8, 4, 2, 4, 2, 4, 8, 6, 10,
6, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 12, 10,
2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10,
8, 4, 6, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4,
6, 8, 4, 6, 2, 10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2,
4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 6, 4, 2, 4, 8, 10,
8, 4, 6, 2, 6, 6, 4, 2, 4, 14, 4, 2, 4, 2, 10, 2,
10, 2, 4, 2, 4, 6, 2, 10, 2, 10, 8, 6, 4, 8, 4, 6,
8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 6,
6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 4,
2, 10, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 12, 6, 4,
6, 2, 4, 8, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2,
10, 8, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 10, 6,
8, 6, 4, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 6, 6, 10,
2, 6, 4, 2, 4, 12, 12, 2, 4, 2, 10, 2, 6, 6, 4, 6,
6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6,
2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 16, 2,
0};
/* BELOW, This QBASIC program was used to generate the above table.
BASIC is uniquely suited for quick output of dinky things like
that (no compiling).
10 DIM a, b, c, d AS INTEGER
50 CLS : a = 0: b = 1: OPEN "C:\CANDIFFS.TXT" FOR OUTPUT AS #1
90 FOR d = 17 TO 30031 STEP 2
IF (((d MOD 3) > 0) AND ((d MOD 5) > 0) AND ((d MOD 7) > 0)) THEN
IF (((d MOD 11) > 0) AND ((d MOD 13) > 0)) THEN
c = d - b
b = d
PRINT #1, RIGHT$((" " +RTRIM$((LTRIM$(STR$©))) + ", "), 4);
IF a MOD 16 = 15 THEN
PRINT #1,
END IF
a = a + 1
END IF
END IF
NEXT d
CLOSE #1
END
*/
// AFTERWARDS, of course, CANDIFFS.TXT was copied/pasted/edited in
// this file. The tail-end zero was added here, to be an
// end-of-table marker.
//////////////////////////////////////////////////////////////////////
// BEGIN: WinMain is the primary/required starting point of any
// Windows program
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
LPSTR szCmdLine, int iCmdShow)
{ static char szAppName[] = "PrmPress";
MSG msg;
WNDCLASS wndclass;
cp = szCmdLine; // make global; prevent compiler warning
previnst = hPrevInstance; // make global; prevent compiler warning
// Prepare a fixed-width font
hfont1 = CreateFont(0, 7, 0, 0, 0, 0, 0, 0, ANSI_CHARSET,
OUT_DEFAULT_PRECIS, CLIP_CHARACTER_PRECIS,
DEFAULT_QUALITY, (FIXED_PITCH | FF_MODERN),
"SimpleFixed"); // NO UNDERLINE
/* (Copied from Language Reference)
CreateFont
(int nHeight, // logical height of font (0=default)
int nWidth, // logical average character width
// (0=default, using 7)
int nEscapement, // angle of escapement (0=default)
int nOrientation, // base-line orientation angle(0=default)
int fnWeight, // font weight (0=default)
DWORD fdwItalic, // italic attribute flag (0=False)
DWORD fdwUnderline, // underline attribute flag (0=False)
DWORD fdwStrikeOut, // strikeout attribute flag (0=False)
DWORD fdwCharSet, // character set identifier, using
// ANSI_CHARSET
DWORD fdwOutputPrecision,// output precision, using default
DWORD fdwClipPrecision, // clipping precision, using SOME
DWORD fdwQuality, // output quality, using default
DWORD fdwPitchAndFamily, // pitch and family,
// using Fixed and no 'serif"
LPCTSTR lpszFace); // address of typeface name string
*/
// FINALLY READY TO CREATE A WINDOW FOR THIS PROGRAM
//wndclass.Size = sizeof(wndclass);
wndclass.style = CS_HREDRAW | CS_VREDRAW;
wndclass.lpfnWndProc = WndProc;
wndclass.cbClsExtra = 0;
wndclass.cbWndExtra = 0;
wndclass.hInstance = hInstance;
wndclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
wndclass.hCursor = LoadCursor(NULL, IDC_ARROW);
wndclass.hbrBackground = (HBRUSH)GetStockObject(LTGRAY_BRUSH);
wndclass.lpszMenuName = NULL;
wndclass.lpszClassName = szAppName;
//wndclass.hIconSm = LoadIcon(NULL, IDI_APPLICATION); //NOT USED
RegisterClass(&wndclass);
hwnd = CreateWindow(szAppName, "Prime Compression",
WS_CAPTION | WS_VISIBLE,
5, 5,
575, 130,
NULL, NULL, hInstance, NULL);
ShowWindow(hwnd, iCmdShow);
UpdateWindow(hwnd);
// Begin main Windows Program Loop; ends when a message returns zero
for(;;)
{ if(GetMessage(&msg, NULL, 0, 0))
{ TranslateMessage(&msg);
DispatchMessage(&msg);
}
else
break; // GetMessage pulled a WM_QUIT and returned zero; exit!
}
// BEGIN ORGANIZED EXIT PROCESS
// CLEAN UP ALL ALLOCATED MEMORY
return(msg.wParam); // PRMPRESS.EXE program terminates here
}; // END OF WinMain()
//////////////////////////////////////////////////////////////////////
// Critical Window Procedure: Windows passes User-Activity messages to
// it, for processing
LRESULT CALLBACK WndProc(HWND hwnd, UINT iMsg, WPARAM wParam,
LPARAM lParam)
{ static HDC hdc;
static PAINTSTRUCT ps;
GetClientRect(hwnd, &rect); // Get rectangular screen region upon
// which text will be displayed
switch(iMsg)
{/* case WM_CREATE: // All initializations already done;
return(0); // ignore WM_CREATE messages
*/
////
case WM_CHAR:
GetKeyNameText(lParam, keynam, 32);
if(!strcmp(keynam, "Esc")) // Quit
{ PostQuitMessage(0);
return(0);
}
if(!strcmp(keynam, "Space"))
L = 1;
else
L = (S_16)strlen(keynam);
if (working == 0) // Other keystrokes ignored when this flag set
{ ch = (char)toupper((int)wParam);
if((L == 1) && (ch >= 'A') && (ch <= 'Z'))
if(task == 0)
prmdrv[0] = ch;
InvalidateRect(hwnd, &rect, 0); // Ensure when flowing,
} // the window is updated
// NOTE: Every WndProc() "case" that is processed is normally
// expected to return(0). HOWEVER, in this program we want
// keystrokes to immediately lead to window-redraws. SO:
// return(0); // FLOW TO WM_PAINT FOR ACCEPTED KEYS
// (use the return(0) in WM_PAINT)
////
case WM_PAINT:
if(painting)
return(0);
painting = 1; // multiple calls here will be rejected
hdc = BeginPaint (hwnd, &ps);
SetBkColor(hdc, 0x00C0C0C0); // reasonably light gray
oldcolr = SetTextColor(hdc, 0x00000000);// black
SelectObject(hdc, hfont1); // fixed font
SetTextColor(hdc, 0x00008000); // moderately dark green
TextOut(hdc, // device context
1, 2, // LOGICAL (not pixel) X and Y coordinates
"THANK YOU, for choosing this prime-generating tool.",
51); // length of above string to display
SetTextColor(hdc, oldcolr); // black
TextOut(hdc, 1, 30, "Press Letter of Drive able to hold "
"200,000,000 primes (100 MegaBytes):", 70);
TextOut(hdc, 500, 30, prmdrv, 1);
if((task == 0) && (prmdrv[0] != ' '))
{ tmp1 = GetLogicalDrives();// Bitmap of available drives
// 1=A, 2=B, 4=C, 8=D, etc, 0=fail
if((tmp1 & (1 << ((S_16)(prmdrv[0] - 'A')))) == 0)
{ MessageBox(NULL, "That drive is not available", "ERROR",
MB_OK | MB_ICONSTOP);
prmdrv[0] = ' ';
}
else
{ task = 1;
working = 1;
PostMessage(hwnd, WM_COMMAND, // **** BEGIN TASK! ****
123456789, 987654321); // with this indicator
} }
if(task == 1)
{ TextOut(hdc, 1, 58,
"Total Remaining Blocks of Numbers to Process:", 45);
TextOut(hdc, 1, 86,
"Program automatically exits when finished, "
"or abort with ESC.", 61);
task = 2;
}
if(task >= 2)
{ sprintf(tmpstr, "%5.5d", todo);
TextOut(hdc, 330, 58, tmpstr, 5);
}
EndPaint(hwnd, &ps);
painting = 0;
return(0); // END OF WM_PAINT
////
case WM_COMMAND:
if((wParam == 123456789) && (lParam == 987654321))
{ sprintf(dirstr, "%s:\\PRIMES", prmdrv);
SetLastError(NO_ERROR);
CreateDirectory(dirstr, NULL);
ret = (S_16)GetLastError();
if ((ret != NO_ERROR) && (ret != ERROR_ALREADY_EXISTS))
{ sprintf(tmpstr, "QUITTING! Code %d regarding Directory %s",
ret, dirstr);
MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
PostQuitMessage(ret);
return(0);
}
// Prepare work area. Note that all primes smaller than 65536 can be
// used to find all primes that fit in 32 bits. There are 6542 primes
// smaller than 65536. They will be stored in the prms[] array, each
// with a special pointer-value which will be explained later.
for (L=0; L<13084; L++)
prms[L] = 0; // Erase the primes/pointers storage array
ti = tbl + 1; // Initialize pointer to second value in
// candidate-increment table
bi = buf;
by = 1; // Initialize first compressed-byte
// to claim that ONE is a prime
bt = 2; // Initialize first flag-bit-setter
// to be used with first tbl[] entry
grand = 1; // set this as a flag for later initialization
cand = 17;
ttl = 6; // primes 2,3,5,7,11,13 are not found by this sieve
ixp = dex; // initialize index-file-buffer pointer
ret = 0;
if(task == 2)
{ sprintf(dirstr, "%s:\\PRIMES\\COMPRESS.PRM", prmdrv);
prmfil = fopen(dirstr, "wb"); // try to open file as binary
if(prmfil == NULL) // failed
{ sprintf(tmpstr, "QUITTING! Could not create compressed "
"Primes File:\n%s", dirstr);
MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
PostQuitMessage(PRM_ERR_OF); //Opening File error (code 3)
return(0);
}
task = 3;
}
while ((!ret) && (todo))
{ if(0 < (ret = FindPrimes()))
{ PostQuitMessage(ret); // any of several possible errors
fclose(prmfil);
return(0);
} }
if((!ret) && (!todo))
{ *bi++ = by; // Save last (probably unfinished)
// byte in output buffer
fwrite(buf, 1, (bi - buf), prmfil);
fclose(prmfil);
*ixp++ = ttl; // Save final count of primes associated
// with last table-usage
sprintf(dirstr, "%s:\\PRIMES\\CMPRMDEX.QNT", prmdrv);
dexfil = fopen(dirstr, "wb"); // try to open file as binary
if(dexfil == NULL) // failed
{ sprintf(tmpstr, "QUITTING! Could not create "
"Primes Index File:\n%s", dirstr);
MessageBox(NULL, tmpstr, "ERROR", MB_OK | MB_ICONSTOP);
PostQuitMessage(PRM_ERR_OF);// Opening File error (code 3)
return(0);
}
fwrite(dex, 2, (ixp - dex), dexfil); // Index file begins
// with a 64-bit total (1st is zero)
fclose(dexfil);
PostQuitMessage(0); // PROGRAM FLOW COMPLETED;
// BEGIN PROPER END-OF-PROGRAM
return(0);
}
}
break; // ignore all other WM_COMMAND messages
////
case WM_DESTROY: // Clean-up work goes here, before ending
// overall prime-generate/compress program
PostQuitMessage(0); // Note memory allocations freed at end of
// WinMain()
return(0); // Always return Zero from any Windows
// message processed
} // All Windows messages not handled in switch block must be
// processed below
return(DefWindowProc(hwnd, iMsg, wParam, lParam));
}; // END OF WndProc()
/******************** MISC SUBROUTINE FUNCTIONS *********************/
S_16 ProcessMessages(void)
{ static MSG mesg; // Make this multi-byte structure static so doesn't
// go on the stack.
ret = 0; // Initialize return-value-variable to Everything-is-OK.
// Below, seek anything in Windows Message Queue for this program
while(!ret && PeekMessage(&mesg, NULL, 0, 0, PM_NOREMOVE))
{ if(GetMessage(&mesg, NULL, 0, 0)) // PeekMessage() found something
{ TranslateMessage(&mesg);
DispatchMessage(&mesg);
}
else // GetMessage pulled a WM_QUIT
{ PostQuitMessage(0); // Must put it back in Messge Queue for
// primary loop in WinMain()!
ret = 1; // Tell this while() loop AND the calling
// function to quit.
} } // Otherwise loop til processed all
// accumulated Messages in the Queue
return(ret); // Return-value ret will be 0 when no
// messages (remaining) in Queue
};
// Each call to this function seeks primes that fall within a range of
// 65536 numbers. The goal of this PRMPRESS program is to find all
// primes that fit in 32 bits; there will be 65536 calls to this
// function. Each found group will be compressed/appended to a single
// long file. (Below, most variables having names ending in i are
// used for indexing into arrays.)
S_16 FindPrimes(void)
{ for(L=32767, ci=cnds; L>=0; L--) // We will only process the 32768
// ODD numbers in each block of 65536
*ci++ = (U_08)1; // Initialize candidate buffer to all ONEs,
// which will be simple prime/not-prime flags
lim = cnds + 32768; // set a Limit of end of candidate-testing area
if(todo == 65536) // If this is first call to this function, we want
// to fill up the prms[] array with the values
// needed to find all the primes in all the OTHER
// 65535 blocks.
{ pri = prms; // Initialize pointer to array of primes and pointers
*pri++ = 2; // Set first prime in array; skip to slot for pointer
// (then skip that at start of for-loop below)
for(pri++,ci=cnds+1; ci<lim; )// Point at second candidate-flag
// (represents 3).
if(*ci++) // If prime/not-prime flag indicates a prime
{ *pri++ = (prm = ((ci - cnds)<<1) - 1); // compute/save the
// actual prime. That is, take difference between
// pointers-to-current-byte in the cnds[] array, and
// the start of that array, to get Nth odd number --
// then double via bit-shift and reduce by 1 to get
// the actual odd number. (Reduce, yes! Because
// variable ci has is now pointing at NEXT number.)
for(c2=cnds+((prm * prm)>>1); c2<lim; c2+=prm)// first compute
// location of square of current prime as starting point
// (note bit-shift halving since only odd numbers in array);
// then check to see if it is past work-area limit; as long
// as loop continues, skip through the work-area at intervals
// equal to the current prime.
*c2 = 0; //flag this location in work-area as a not-prime
*pri++ = (U_32)c2; // SAVE CANDIDATE-POINTER AFTER LOOP ENDS
// This is a key to efficiency. In the prms[] array, each
// prime will be associated with such a pointer. It IS the
// place where, if the cnds[] array was larger, the next odd
// number divisible by this prime would be indicated. All we
// have to do is subtract the size of the cnds[] array, and
// this value becomes the starting point in the next block
// of 32768 odd numbers, for more flagging-as-not-prime.
// Note that when the pointer to the square of a prime is too
// big for any immediate flagging, successive subtractions as
// this function is called will quickly bring its value down
// to where it WILL work correctly.
} }// End of processing of all primes smaller than 65536.
else // All of the other 65535 other calls to this function
// (with all 32768 candidate flags initialized to ONE)
{ for(L=1, pri=prms+2; L<6542; L++) // For every prime smaller than
// 65536, except for the first (2)
{ prm = *pri++; // fetch the prime
for(ci=(U_08 *)(*pri-32768); ci<lim; ci+=prm)
// Fetch/adjust pointer associated with current prime; test for
// beyond-end-of-cnds[]-array; during loop adjust pointer for
*ci = 0; // flagging candidate as composite
*pri++ = (U_32)ci; // Save new pointer value and prepare to
// repeat for next prime in prms[] array
} }
// Now to compress the data among the current array of 32768
// candidate-flag-bytes. Note this compression scheme is only for
// primes larger than 13. So, previously, variable 'grand' (below)
// was initialized to ONE. That means, on the very first call to
// this function, it is not greater than 13 in following test. Thus
// we can reinitialize grand to 17, the first prime that will be put
// into the compressed-data file, and we can set L to indicate that
// we want to skip the bytes in the cnds[] array that represent the
// odd numbers 1, 3, 5, 7, 9, 11, 13, and 15. On all other calls to
// this function, grand will be greater than 13, so it will be left
// alone while L is set to Zero, because we want to be able to check
// any of the odd numbers that are flagged in the cnds[] array.
L = (grand > 13) ? (S_16)0 : (grand=17,(S_16)8);
lim = buf + 4096; // reset Limit variable to end of output buffer
for(ci=cnds+L; L>=0; L++, grand+=2, ci++) // Set candidate-index to
// correct starting place in cnds[] array; test for L changing
// from +32767 to -32768 at end of loop; while loop continues,
// adjust grand for next odd number and bump index to next flag.
// Below, recall 'cand' was initialized to 17. It will be bumped
// by values taken from the cycle-of-non-divisibility table.
{ if(grand == cand)// ONLY when this happens MIGHT we have a prime
// among the flag-bytes of the cnds[] array
{ if(*ci) // current candidate-flag-byte indicates a prime
{ by |= bt; // Set a bit in compressed-data byte; each byte
// represents 8 odd numbers DERIVED FROM THE NON-
// DIVISIBILITY TABLE, and only the actual primes
// are flagged with ONE-bits.
ttl++; // count total number of primes in current block
// of 30030 numbers, for the Index File
}
if(bt == 128) // check for last possible bit-value that fits
// in one byte
{ bt = 1; // reset bit-setter to first bit for next byte
*bi++ = by; // save current byte in output buffer
if(bi == lim)// Test for end of buffer
{ fwrite(buf, 1, 4096, prmfil); // save buffer to file
bi = buf; // reset buffer index pointer
}
by = 0; // reset compressed-data byte for next 8 numbers
}
else // as long as we haven't used highest bit-value
bt <<= 1; // double for next bit-that-might-be-set
cand += *ti++; // set next candidate that grand must match,
// by adding a non-divisibility-table value
if(!*ti) // reached end of candidate-increment table?
{ ti=tbl; // reset to start of table
*ixp++ = ttl;// Save current count of primes (in the just-
// compressed block of 30030 numbers) to the
// index-file buffer.
ttl = 0; // reset counter for next Indexed batch of primes
} } }
todo--;
InvalidateRect(hwnd, &rect, 0); // make window update-able
ret = ProcessMessages();
return(ret);
};
|
|
