The Prime Machine
The applet on this page lets you explore the set of prime
numbers. You do need a
greater than 1 that can be divided without remainder only by
itself and by 1. Natural numbers n that can be
divided by a number less than n and greater than 1
are composite numbers. The prime machine
finds prime numbers using the
Sieve of Eratosthenes
and lets you study and explore those prime numbers.
When you first click on the above applet a control window
pops up. It should look like this:
The most important item in that window is the text field in
the center of the second row, the one with the fetching
dark red background.
Everything happens with respect to the number in that field.
Let's call it N. Initially, N=100 (that value
lets you explore the prime numbers in a familiar range).
Let's go though the rows of the control panel.
The green buttons
scroll down or up through the internally
computed (rather than downloaded!) list of prime
numbers. The number of angular brackets
determines the speed of the scroll:
< or >: a step of 1
down or up; respectively.
<< or >>: down
or up to the next prime number.
<<< or >>>
: down or up all the way to the end
of the current list. The lower end is
of course the smallest prime number,
The gray or red button STOP will
interrupt a computation of new primes that might
be in progress.
It is effective only when it is red.
The blue button quit will cause all
computation to stop and the control window to
disappear. You can achieve the same affect by
clicking on the applet, or typing "x",
"X", "q", or "Q"
in the control window.
button draw causes a drawing to be
displayed that illustrates the distribution of
prime twins and the prime number theorem.
More on that below.
The Status Label displays the following
types of information:
with the word "Ready".
This means all is ready for a new
possibly with a number in it. This
means the Sieve of Eratosthenes is being
used to compute prime numbers. The
number in the red field indicates the
estimated number of seconds to
completion. That number changes as time
passes, but the estimate is not very
reliable. It's usually too high, unless
your computer is swapping heavily.
possibly with a number in it.
This means that the information in the
white text labels of the control display
are being recomputed. The number
indicates the estimated number of
seconds to completion. It is computed
only once, and not very reliable either.
possibly with the word
Memory in it. This means that in
the last attempt to extend the range of
prime numbers your computer ran out of
memory. The program will attempt to
restore the display and the list of
primes to the previous values. If that
does not work then everything is
returned to the the default values
(corresponding to N=100.
Row 2. N is the number around which
everything revolves. You can change it via the green buttons in row 1,
or you can just edit the text window. To the left of
N (unless N=2 ) is the largest
prime number less than N and to the right
(unless we are right at the limit of the current range)
is the smallest prime number greater than N
. The window to the right turns gray if there is
no prime number between N and the end of the
current range, and the window to the left turns gray
Row 3. This label exhibits the closest Prime
Twins above and below N. A prime twin is a pair of
prime numbers that differ by 2. Although this question
has been much studied, nobody knows how many prime twins
there are. There may be finitely many or infinitely
many. If you figure out the answer,
be sure to drop me a message
so I can update this page!
Row 4 is devoted to illustrating
the prime number theorem.
phi is the number of primes less than or equal
to N. N/log(N), where log is
the natural logarithm, denotes an approximation
of phi that is known to get arbitrarily
accurate, in the sense that the ratio phi/(N/log(N))
converges to 1 as N goes to infinity.
That ratio is displayed. For the range of numbers that
this applet can handle (up to N = a few tens of
millions) the ratio is almost constant and varies from
about 1.12 to 1.06.
Row 5 shows the prime factorization of
Row 6 is dedicated to the Goldbach Conjecture
which asserts that every even number greater than 2
can be written as the sum of two prime numbers. If
N>2 is even then this row displays the following
Nobody knows if the Goldbach conjecture is true or not,
even though countless mathematicians and probably
millions of high school kids have tried to settle the
question. But as in the case of the number of prime
twins, do let me know if you find the answer.
I'll be pleased to make your acquaintance.
The number of ways in which N can be
written as the sum of two prime numbers.
Two prime numbers that add to N.
Initially this is the pair where the two prime
numbers are as close together as possible.
However, you can scroll up and down the list
using the + and - buttons.
Row 7. I increase the version number by an
appropriate amount every time there is a significant
change. The run number indicates the number of times
this program was activated since November 7, 1996.
How does it work?
When starting up the applet computes all prime numbers from
2 to 2N. It does this by using a modification of
Sieve of Eratosthenes
that only considers odd numbers and is about twice as fast
and uses half as much memory as the original sieve. As
mentioned above, the default value of N is 100. If
the value of N (perhaps entered though the
textfield) exceeds the range of numbers covered a new
computation is started automatically. The larger the new
value of N, the longer the computation will take,
and the more memory it will require.
A Graphical Illustration of the Prime Number Theorem
The celebrated Prime Number Theorem states that
number of primes <= N
lim --------------------- = 1.
where log denotes the natural logarithm. It is pretty
amazing to have such a tight connection exists between areas of
mathematics (logarithms and prime numbers) that seem so
disparate! For more information consult any text on Number
Theory, for example those listed on my
Prime Number Page.
Unfortunately, the ratio N/log(N) behaves very much
like a linear function, so the large scale behavior of prime
numbers is not readily apparent. You can display the number
of prime twins, phi, and N/log(N) by
pressing the yellow draw button in the first row of the
control panel. (Press the button again to make the drawing
For N=10,000 you get the display illustrated in the
nearby figure. N varies along the horizontal axis. Red
indicates the number of prime twins, green the approximation
x/log(x) (counted from the horizontal axis, and
blue the actual number of primes (also counted from the
horizontal axis). Think of red being in front of green, and
green in front of blue. You can only see the top of blue
and the top of green, but all of red. According to the
prime number theorem, in the limit as N tends to infinity
green and blue become identical. It also appears from the
picture that the number of prime twins grows linearly with
N which, if true, would imply that there are
infinitely many prime twins. Click
here or on the picture
to see the corresponding display for N=100,000,001
which is close to the largest value that I can reasonably
handle on my machine. It actually does not look much
different, although the blue wedge is a little narrower. You
may also like to explore drawing the picture for small
values of N, to illustrate the discrete
nature of the prime distribution.
Note: If your machine is at all like mine then
everything will become sluggish and things may not work quite
right if you use a lot of memory. So you may want to be careful
about choosing very large values of N.
Running Standalone and Downloading
You may download the byte code of this software and incorporate
it into your own web pages or run it on your system in a
standalone mode. You need the following Java classes:
When you click on these links (which point to binary files)
you'll probably see something strange on your system.
However, you should be able to download the files properly
in spite of their appearance.
Prime is the class that calls all others. To run the
software in standalone mode on a Unix system just type
java Prime in the directory that contains your class
files. If you want to base an Applet on your files make
sure you specify the code base (the directory containing
your class files) similarly as in the html code of this
page. The code base must be accessible over the net,
otherwise you get a security exception and things don't work
If you do download the software I invite you to
let me know
so that I can put you on my mailing list and inform you
about future improvements. Of course, also let me know if
you have any troubles.
There is no help information built into the program (at
least not yet). This page is intended to be the
documentation for the program. So you may want to copy the
page, print it, or provide a link to it.
When the applet is run from inside a browser, clicking
twice on the applet makes the control window disappear
and reappear with resized text labels that may be too
small for subsequent computation. To overcome this do
the computation for N as large as you wish, and
then click twice on the applet again.
Return to Peter Alfeld's Home Page.