Mencher on the Programmer's Corner (Gary Smith's BBS) in Washington, D.C.
(Columbia, MD) and is based heavily on Bill Parke's response contained in
PRIMES14. For completeness, this file includes PRIMES14.ZIP.
PRIMES14 allowed prime numbers to be generated for any range of numbers
between 1 and 1,048,575, and was written in assembly language for the 8088
cpu. LMPRIME1 goes a step further and extends the range to 4,294,967,295 but
takes advantage of, and requires, an 80386 processor. The size of the
program is larger than Bill's PRIMES14, but is still small enough
to be contained within 1 cluster (2048 bytes) on most hard disks.
The number of primes less than a given number, x, may be estimated by the
following formula attributed to the 19th century German mathematician,
P(x) = [Li (x)] - .5 x Li (ûx), where Li(x) = ³ dt / ln t
The accuracy of this formula may be judged by the following table:
x of Primes less Li (x) P(x)
100 25 29 27
1,000 168 177 170
10,000 1,229 1,245 1,231
100,000 9,592 9,629 9,594
1,000,000 78,498 78,627 78,538
10,000,000 664,579 664,917 664,686
100,000,000 5,761,455 5,762,208 5,761,586
1,000,000,000 50,847,568 50,849,234 50,847,517
The syntax for running LMPRIME1 is
LMPRIME1 n1 n2 [/] [/?]
where n1 and n2 are decimal digits (no comma delimiters) with
0 < n1 < n2 < 4,294,967,295
The program will give a listing of all primes between n1 and n2 and
a count of the number of such primes.
The optional / will suppress listing individual primes, supplying only
the count of the number of primes.
The program is compatible with DOS 5, so that supplying only the argument
/? will produce a small help message. For those using the DOS help
facility and DOSHELP.HLP, the DOS command HELP LMPRIME1 will also produce
the help message (provided LMPRIME1 has been added to DOSHELP.HLP).
The number of primes contained on each line of output is dependent on the
size of the largest prime. For example, with an 80-column screen,
LMPRIME1 1 90 will produce 24 primes on one line, while
LMPRIME1 4000000000 4000000200 will require two lines to produce 8 primes.
The program can also be used with either a 40-column screen or a 132-column
If your system contains an 80x87 math coprocessor, LMPRIME1.COM contained
in this file does not make use of the math chip. However, the source code
contained in LMPRIME1.ASM can easily be modified to take advantage of the
80x87 by changing the definition of IS8087 from 0 to 1. There is no major
speedup in calculation time; however the resulting .COM file will be smaller.