Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Eratosthenes of Cyrene

A versatile scholar, Eratosthenes of Cyrene lived approximately 275-195 BC. He was the first to estimate accurately the diameter of the earth. For several decades, he served as the director of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived. Eratosthenes died at an advanced age from voluntary starvation, induced by despair at his blindness.

Here are some links to Eratosthenes related web pages:

• A worldwide experiment based on Eratosthenes original computation of the Earth's circumference.
• A page on Ancient Geography.
• Maps, lists, resources, and links pertaining to ancient Greek mathematics.
• The library of Alexandria.

The Sieve of Eratosthenes

Eratosthenes also conceived the "Sieve of Eratosthenes ", a method of identifying prime numbers. If you have a Java compatible browser you can use that sieve right here, from this Applet:

However, your browser does not support Java. If it did you would not see this message! Get a java compatible browser such as Netscape, of a sufficiently advanced version.

What is the Sieve of Eratosthenes?

A prime number is a natural number 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 Sieve of Eratosthenes identifies all prime numbers up to a given number n as follows:

1. Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
2. Mark the number 1 as special (it is neither prime nor composite).
3. Set k=1. Until k exceeds or equals the square root of n do this:
   • Find the first number in the list greater than k that has not been identified as composite. (The very first number so found is 2.) Call it m. Mark the numbers

      2m, 3m, 4m, ... 
     

     as composite. (Thus in the first run we mark all even numbers greater than 2. In the second run we mark all multiples of 3 greater than 3.)
   • m is a prime number. Put it on your list.
   • Set k=m and repeat.

This is exactly what the applet does. If the natural numbers are arranged in a rectangular array than marking the composites gives rise to interesting patterns. The Figure nearby shows one of these patterns (the prime numbers from 2 through 12,743), but seeing the pattern develop is much more interesting than seeing the static final result. Experiment with various options yourself! Click here or on the pattern to see a similar pattern made of boxes 2 by 2 pixels large, forming a 529 by 369 rectangle, and showing all primes up to and including 195197.

Since this is an educational page I'll give you a home work problem: Explain the vertical streaks that seem to be present in the pattern. Once you are done with that, explain why there are no horizontal streaks! Send me your answer!

The remainder of this page is

A User's Guide to the Sieve of Eratosthenes Applet

A quick tour

To see how it works, do the following:

• Click on the applet. Two windows, called " Sieve of Eratosthenes Controls" and "The Sieve of Eratosthenes" will pop up on your screen. They should look like the images nearby on this page and fit on your screen. Arrange them conveniently so that you can see both windows without obstruction. Let's call them the control panel and the drawing window. The boxes in the drawing window should form a 10 by 10 array representing the numbers 0 through 99 arranged as we read (i.e., from the top left corner to the bottom right corner). Check you understanding by clicking on some of the black boxes and seeing the corresponding numbers show up in the textfield labeled pick: in the 3rd row of the control panel. The blue box corresponds to 1, which as we saw is different from all other numbers. The number zero is not shown since it isn't a natural number.

• Move the cursor into the drawing window and hit the key "s" (for "step"). The square corresponding to the number 4 is colored white. That means it is not a prime number (since it is a multiple of 2). Hit "s" again. The number six square is colored white. Do this a few times until you see what's happening.
• Hit the key "p" (for "prime"). The multiples of 2 will be finished off.
• Hit "s" again (or "p") to see what happens to the multiples of 3.
• Hit "a" (for "all") to see the rest of the process. The prime numbers from 2 to 100 are now marked with black boxes. Click on some of them to see that they do indeed correspond to the prime numbers.
• In the second row of the control panel, change the number in the textfield labeled "size" to 2. (To do this, highlight the 20 that's in the field, type 2, and hit return.) Then click on " do it all" in the first row of the control panel. You'll see patterns emerge as the Sieve of Eratosthenes proceeds, and the final picture (if you didn't resize the drawing window) should look like the pattern in the image above..
• If the process is too slow for your taste, do this:
  1. Click on "reset" in the control panel.
  2. Change "Delay" in the second row of the control panel to 0.
  3. Click on "Do it all".
  4. If this is still not fast enough, select " Fast" in the upper right corner of the control panel, click on "reset ", and click on "do it all" again. Now the sieve will run as fast as it can on your machine.

Details of the Operation.

To Start

Starting is very simple. You click on the applet.

To Quit

Quitting is also very simple. It can be accomplished in a number of ways:

• Click in the applet on your web page.
• Click on the QUIT button in the control panel.
• Type "x", "X", "Q", or "q" in any window.
• Quit your browser.

The Control Panel

Let's run through the rows of the control panel:

1. Row 1.
   • do it all! This button starts the sieve, which will run to completion (unless it is interrupted).
   • do 1 prime will start the sieve and let it run until the multiples of the current prime are all marked. If the button is clicked during a full run (started by do it all! ) the run will stop after the current prime is completed.
   • do 1 step similarly will take 1 step of the sieve and then cause it to stop. It will also stop a run in progress.
   • reset will return the drawing window to its original state.
   • resize is required for one of the methods for resizing the drawing window. To use it, resize the drawing window manually and then click on it.
   • The safe/fast menu will select the safe or fast mode. In the fast mode the program runs a little faster and uses less memory. In the safe mode you can partially cover and uncover, or even close and reopen, the drawing window and its contents will be restored.
2. Row 2.
   • Size: This is the size (in pixels) of the square corresponding to the numbers 1, 2, ... . Changing the size will also cause the drawing window to be reset. The minimum possible size is 1. If the size is greater than 4 then each square is surrounded by a green outline. Altering the size will increase or decrease the n but not the size of the drawing window.
   • Delay: This is the delay in milliseconds used when marking a number as composite. During the delay the corresponding square is rendered in red. For large investigations the delay should be set to zero, but for demonstrations larger values may be suitable.
3. Row 3
   • Primes: The text window with the buttons "-" and "+" next to it displays the primes that have been found. By default the largest one is displayed. You can go up and down in the list by clicking on the "-" and "+" buttons, respectively. Overwriting the number in the text field will cause the next largest prime to be displayed (within the range of primes found by the sieve).
   • pick: Clicking on one of the squares in the drawing window will cause the corresponding number to appear in the text field. This is useful for orienting yourself.
4. Row 4. The text windows give the horizontal and vertical extents extent of the drawing window (in boxes) and the length of the list used in the sieve. You can resize the drawing window by specifying the horizontal and vertical extents in the text windows.
5. Row 5. I increase the version number whenever there is a significant change in the code, by an amount roughly proportional to the change. If you are using an old version then you should probably replace it with the newer version provided here (see the downloading instructions below). The Run # is the total number of runs since November 1, 1996, by all copies of the program, to date. I'm not trying to spy on you, but I am curious how much the program is used, and I'm also fascinated by the technology. The count is obtained by sending an inquiry to my system which returns the current count. This ability to communicate over the net opens a lot possibilities which are as yet not even recognized. If my server daemon is down the program runs fine without indicating a count.

The Drawing Window

You can resize the drawing window in several ways:

• Change the horizontal or vertical extent of the drawing area in the control panel. This will interrupt any drawing in progress.
• While no drawing is in progress, change the size of the window manually, and then click on "resize ".

You can also control the drawing action via the key board as follows:

• "a" or "A" are the equivalent of do it all!
• "p" or "P" are the equivalent of do 1prime
• "s" or "S" are the equivalent of do 1 step
• "r" or "R" are the equivalent of reset
• "d" or "D" set the delay equal to zero and accelerate the drawing.
• "x", "X", "q" or "Q " are the equivalent of quit

Getting the most out of your applet.

To compute the largest possible range of primes on your machine do the following:

1. Click on "reset" or otherwise make sure the drawing has stopped.
2. Set "size" to 1.
3. Make the drawing window as large as possible, and lower the window, or close it.
4. Click on "resize".
5. Set the delay to zero and click on "do it all! ", or with the cursor in the drawing window type "d" and "a".

On my machine this process gives rise to a window that 1254 by 894, with n=1,121,075..

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:

• Sieve.class
• ControlSieve.class
• DrawSieve.class

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.

Sieve is the class that calls all others. To run the software in standalone mode on a Unix system just type java Sieve 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 right.

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.

Known Bugs

This is a list of known bugs. I'm working on them, but at the moment it's not clear to me how to find and correct them (otherwise I'd fix them immediately). If you have any suggestions, or would like to report other bugs, please write to me!

• Some actions during the drawing process cause the computation to go faster, but at the expense of resisting interruption, and omitting to repaint the drawing window after covering or closing it. These actions include resizing the drawing window or and clicking somewhere in the drawing window. Until this bug is fixed, perhaps you can look at it as a feature!

Return to Peter Alfeld's Home Page.

Designed for netscape and Java.