Prime Solutions Version 1.4

(c) 1991 William C. Parke

The program PRIMES generates the prime numbers from 1 to 1,048,559,
starting with a code containing no more than about 1,000 bytes. It was
stimulated by a Spring, 1991 contest by Howard Mencher on the
Programmer's Corner (Gary Smith's BBS) in Washington, D.C. (Columbia,
MD). PRIMES was written to demonstrate both the economy and speed of
programs written in assembly. [Howard's contest specifically excluded
ASM code.]

The calculation of the primes to 1,048,573 takes less than two seconds
on a 25MHz '386 machine, although printing them to the screen requires a
significantly longer time. Screen-print time could be reduced by a
factor of 1/3 using direct screen video functions. However, this option
would prevent redirected to a file using the DOS command line
redirection function. Of course, another strategy for generating primes
is to store information about their distribution in the data area of the
program. This would allow a faster initialization. However, it requires
significantly more disk space, goes against the requirement of
calculating the primes in the first place, and would not be necessary
even in practice.

There are 82,025 primes from 1 to 1,048,575. (The number of primes
between 1 and N is approximately N/lnN for large N.) A bit map for all
these takes no more than 64K bytes. Thus, it would be possible to
generate and store this prime number table within the data area of a
code which needed primes, such as a factorization algorithm. [The bit
map table itself contains significant redundant information. The ZIP
compression reduces the table by 24%. A formula for any prime would take
up far less space!] Note, however, that the application of prime number
divisions to factorize large numbers is not practical when the number of
digits approaches 50 or more. (For some practical alternatives, see
Knuth, Seminumerical Algorithms, Vol.2 in The Art of Computer
Programming, Second Edition, Addison Wesley, 1981.)

The syntax for running PRIMES is

PRIMES n1 n2

where n1 and n2 are decimal digits (no comma delimitors)
with 0 < n1 < n2 < 1048576.

For example,

PRIMES 10237 10313

will show the primes between these given numbers, inclusive.

The program will also display a count of the number of primes found.

To make a file of the primes, use DOS redirection. For example

PRIMES 1 100,000 > PRIM4

will make a file called PRIM4 with the primes from 1 to 100,000.

History:
Version 1.4 Sped up prime calculation by stopping sieve at square
root of larger prime; corrected bug found by Les Moskowitz.
Version 1.3 drops printing of 2 for large n1. ASM files are included.
Version 1.2 differs from 1.1 by correcting the first prime as 2 rather
than 1, and fixes a bug in PRIMES.