About
Community
Bad Ideas
Drugs
Ego
Erotica
Fringe
Society
Technology
Hack
Phreak
Broadcast Technology
Computer Technology
Cryptography
Science & Technology
Space, Astronomy, NASA
Telecommunications
The Internet: Technology of Freedom
Viruses
register | bbs | search | rss | faq | about
meet up | add to del.icio.us | digg it

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
};
 
To the best of our knowledge, the text on this page may be freely reproduced and distributed.
If you have any questions about this, please check out our Copyright Policy.

 

totse.com certificate signatures
 
 
About | Advertise | Bad Ideas | Community | Contact Us | Copyright Policy | Drugs | Ego | Erotica
FAQ | Fringe | Link to totse.com | Search | Society | Submissions | Technology
Hot Topics
What do you call the main box of the computer?
Comp keeps freezing after bootup :(
Essential Programs Thread
Your tech related job
32-bit OS on 64-bit computer
Split Hard Drive???
computer crashed
Intel's Q6600
 
Sponsored Links
 
Ads presented by the
AdBrite Ad Network

 

 

TSHIRT HELL T-SHIRTS