|
Extracting One Prime Number From a Compressed-Data File
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
PIKPRIME, and use the Project Options Editor/Configuration-Tool to
delete ALL default files, such as "PIKPRIME.RES" or "PIKPRIME.DEF",
and ensure that the ONLY Project file is this one, PIKPRIME.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 PIKPRIME.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 PIKPRIME.EXE should successfully
work as described elsewhere herein. However, if PIKPRIME.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 PIKPRIME.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 PIKPRIME 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 PIKPRIME 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).
PURPOSE OF THIS PROGRAM: The user selects a number N between either 1
and 203,280,221 -- and the program fetches the Nth prime. Or, the
user selects a number between 1 and 4,294,967,296 -- and the program
states whether or not N is a prime. That's all.
*/
////////////////////// 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 PIK_ERR_OM 1
#define PIK_ERR_DA 2
#define PIK_ERR_OF 3
#define PIK_ERR_FR 4
#define PIK_ERR_FW 5
#define PIK_ERR_BD 6
#define PIK_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 FetchPrimeInfo(void);
S_16 ProcessMessages(void);
// Global Variables.
HWND hwnd;
FILE *prmfil, *dexfil;
HFONT hfont1;
HINSTANCE previnst;
RECT rect;
COLORREF oldcolr;
char keynam[] = " ",
tmpstr[300], ch, dirstr[40];
char *cp;
U_08 buf[4096], *by, bt, *tp;
S_16 L, ret, task = 0,
painting = 0, working = 0;
U_16 buf2[150000], *bp, *lim;
S_32 fpb, hi, md, lo;
U_32 tmp1, cand, prm, dex[150000], *ixp, grand;
U_08 skpd[7] = {1, 2, 3, 5, 7, 11, 13};
/* 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 PIKPRIME 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 PIKPRIME program will also use an index file. It consists of
two-byte values indicating how many primes exist in each range of
30030 numbers. There are 143,023 entries in this file, so its size is
286,046 bytes. The PIKPRIME program loads the entire file into a
table of 4-byte numbers. Each table entry will a cumulative SUM, such
that the Nth number in the table is the sum of the first N numbers in
the index (the last entry will have the value 203,280,221). Each
adjacent pair of values indicates a RANGE in which a desired Nth prime
might be found; a binary search of the table will quickly locate the
correct range. 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[] = "PikPrime";
MSG msg;
WNDCLASS wndclass;
cp = szCmdLine; // make global; prevent compiler warning
previnst = hPrevInstance; // make global; prevent compiler warning
// Let's start by finding out if this program can actually do its job.
// Do the files COMPRESS.PRM and CMPRMDEX.QNT exist?
tmp1 = GetLogicalDrives();// bitmap of available drives 1=A, 2=B, 4=C, 8=D, etc, 0=fail
ch = 'C';
for(cand=4; cand>0; cand<<=1)
{ if((tmp1 & cand) == cand)
{ sprintf(dirstr, "%c:\\PRIMES\\COMPRESS.PRM", ch);
prmfil = fopen(dirstr, "rb");
if(prmfil != NULL)
{ fpb = 0; // file-position-byte
sprintf(dirstr, "%c:\\PRIMES\\CMPRMDEX.QNT", ch);
dexfil = fopen(dirstr, "rb");
break; // quit for() loop regardless of existence of file, because have other file
} } // assume compressed-prime file does not exist; try next drive
ch++; // 'D, 'E', etc
}
if((prmfil == NULL) || (dexfil == NULL))
{ MessageBox(NULL, "Files COMPRESS.PRM and CMPRMDEX.QNT not available!",
"ERROR", MB_OK | MB_ICONSTOP);
}
else
{ fread(buf2, 2, 143023, dexfil); // load the index to the primes-data file
fclose(dexfil);
lim = buf2 + 143023;
ixp = dex;
cand = 0;
for(bp=buf2; bp<lim; )
{ cand += *bp++; // accumulate number of primes in this indexed block
*ixp++ = cand; // save the accumulations for later binary search
}
cand = 0;
L = 0;
// 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); //UNUSED
RegisterClass(&wndclass);
hwnd = CreateWindow(szAppName, "Prime Q & A",
WS_CAPTION | WS_VISIBLE,
5, 5,
400, 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
if(prmfil != NULL)
fclose(prmfil);
if(dexfil != NULL)
fclose(dexfil);
return(msg.wParam); // PIKPRIME.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) // All other keystrokes ignored when this
// flag-variable is changed
{ ch = (char)toupper((int)wParam);
if((!strcmp(keynam, "Enter")) ||
((L == 1) && (ch >= '0') && (ch <= '9')))
InvalidateRect(hwnd, &rect, 0); // ensure when flowing,
// the window is updated
else
return(0); // ignore all other keystrokes
}// NOTE: Every WndProc() "case" that is processed is normally
// expected to return(0). HOWEVER, in this program we want
// DESIRED keystrokes to cause window-redraws.
// 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); // 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-answering tool.",
50); // length of above string to display
SetTextColor(hdc, oldcolr); // black
TextOut(hdc, 1, 30, "Enter a number from 0 to 4294967295:", 36);
TextOut(hdc, 1, 86, "Press ESC to end this program.", 30);
if(task == 0)
{ if((L == 1) && ((cand < 429496729) || (ch <= '5')))
{ cand = (cand * 10) + (ch - '0'); // accumulate overall Number
TextOut(hdc, 262, 30, " ", 10); // Erase previous
// Number
sprintf(tmpstr, "%d ", cand);
TextOut(hdc, 262, 30, tmpstr, 10); // display current Number
TextOut(hdc, 1, 58, /* erase any previous "answer" */
" "
" ", 60);
L = 0;
} // Below, completing the Number is the same as
// asking the Question
if((L > 1) || (cand >= 429496729)) // If Enter or
// too-big-a-number entered
{ task = 1; // prevent keystroke output
working = 1; // ignore keystroke input
if(0 < (ret = FetchPrimeInfo())) // Results are put in prm
// and tmp1 variables
PostQuitMessage(0);
else
{ if(prm) // set to a prime, or to Zero
sprintf(dirstr, "; Prime #%d is %u.", cand, prm);
else
sprintf(dirstr, "; Prime #%u is out of range.", cand);
// below, tmp1 was set to Zero if cand is not a prime
sprintf(tmpstr, "%u is%s prime%s", cand,
(tmp1 ? "" : " not"), dirstr);
TextOut(hdc, 262, 30, "(another!)", 10);// Replace entered
// Number
TextOut(hdc, 1, 58, /* erase any previous "answer" */
" "
" ", 60);
TextOut(hdc, 1, 58, tmpstr, strlen(tmpstr)); // Display
// Answer
cand = 0; // Initialize for next keystroke
// entry/accumulation
L = 0; // Ensure no accidental character-display
// in Window
task = 0; // allow keystroke output
working = 0; // pay attention to keystroke input
} } }
EndPaint(hwnd, &ps);
painting = 0;
return(0); // END OF WM_PAINT
////
case WM_DESTROY: // Clean-up work goes here, before ending overall
// conversion 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()
/********************************************************************/
// Determine if Number in cand is a prime; also find the Nth prime,
// where N=cand
S_16 FetchPrimeInfo(void)
{ if(cand < 17) // for primes not included in compressed data
{ for(tmp1=0,L=0; (L<7)&&(!tmp1); L++)
tmp1 = ((U_32)skpd[L] == cand);// compare cand to a short list
if(cand < 7)
prm = skpd[cand];//also get Nth prime from the list, if possible
}
else if(!(cand & 1) || !(cand % 3) || !(cand % 5) || // Do division
!(cand % 7) || !(cand % 11) || !(cand % 13)) // tests NOT
// embodied in compressed data
tmp1 = 0; // failed divisibility tests by 2,3,5,7,11,13
else // use COMPRESS.PRM data file to determine if cand is a prime
{ prm = cand / 30030; // Integer division figures needed block of
// compressed data
tmp1 = prm * 720; // Number of compressed bytes per block that
// precedes wanted block
fseek(prmfil, ((S_32)tmp1 - fpb) , SEEK_CUR); // Go to appropriate
// file location
fpb = fread(buf, 1, 720, prmfil); // Load a block of
// compressed-prime data
fpb += tmp1; // Set file-position-byte to current location for
// next seek
prm *= 30030; // Compute start of numbers-block that includes
// candidate-variable cand
prm++; // adjust for first number represented by compressed data
by = buf; // set byte-pointer to start of 720 items in buffer
bt = 1; // initialize bit-tester
tp = tbl; // initialize table-pointer
while(prm != cand)
{ prm += *tp++; // add a tbl entry
if(bt == 128)// check for last possible bit-value (in one byte)
{ bt = 1; // reset bit-tester
by++; // advance to next byte in buffer
}
else
bt <<= 1; // double for next bit-that-might-be-tested
} // when loop ends, we now have correct byte and bit to test
tmp1 = ((bt & *by) == bt); // Set this flag to 0 or 1 depending
// on primality
}
// Now to find the Nth prime, where N=cand
if(cand > 203280221) // Too big a value entered for finding Nth
// prime?
prm = 0;
else if(cand > 6) // range of primes represented by compressed data
{ lo = 0; // lowest Index element
hi = 143022; // highest Index element
md = hi >> 1; // Prepare to do a binary search from middle of
// the Index
while (lo != hi)
{ if(cand < dex[md])
hi = md; // set new upper bound (this still might be the
// right block!)
else if(cand > dex[md])
lo = md + 1; // Set new lower bound
// (block following md might be the right one!)
else
break; // Well, well, cand just happened to exactly
// match an Index entry!
md = ((hi - lo) >> 1) + lo;// Get new middle between hi and lo
// (may equal untested lo if hi-lo=1,
// but next loop then finds it or
// makes lo=md=hi)
}
prm = md * 720; // compute which block of compressed file holds N
fseek(prmfil, ((S_32)prm - fpb) , SEEK_CUR); // Go to appropriate
// file location
fpb = fread(buf, 1, 720, prmfil); // Load a block of
// compressed-prime data
fpb += prm; // Set file-position-byte to current location for
// next seek
tp = tbl; // initialize table-pointer
if(md > 0)
{ grand = dex[(md - 1)]; // Fetch total number of primes preceding
// the fetched block
prm = md * 30030; // Initial computation for first possible
// prime in that block
prm++; // Adjust for exactness: first number
// represented by compressed data
bt = 1; // initialize bit-tester
}
else // very first block...
{ grand = 6; // compressed-prime data starts at 7th prime;
// ensure loop below works
prm = 17;
bt = 2; // initialize bit-tester
tp++; // correct table pointer for first block
}
by = buf; // set byte-pointer to start of 720 items in buffer
for(;;) // this loop guaranteed to break
{ if((*by & bt) == bt) // if this is a prime
grand++; // count towards desired N
if(grand >= cand)
break; // exit if N reached
prm += *tp++; // add a tbl entry to create new possible prime
if(bt == 128) // check for last possible bit-value (in one byte)
{ bt = 1; // reset bit-tester
by++; // advance to next byte in buffer
}
else
bt <<= 1; // double for next bit-to-test
} } // when loop ends, variable prm holds the desired Nth prime
ret = ProcessMessages();
return(ret);
};
/********************************************************************/
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
};
|
|