Loading...
Please wait, while we are loading the content...
Similar Documents
Visualizing the Sieve of Eratosthenes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Cox, David N. |
| Copyright Year | 2008 |
| Abstract | Every so often new technology is applied to an ageold problem to produce unexpected results. This article re-examines the Sieve of Eratosthenes. The Sieve is a one-dimensional device for finding prime numbers. The numbers from 2 to n are written as a single, long sequence. Then the multiples of 2 are crossed out but leaving 2. Then the multiples of 3 are crossed out but leaving 3. And so on until the only numbers remaining are the primes. This paper explores what happens if the procedure is converted from one dimension to two. Rather than a single sequence, a matrix is constructed such that in the first row every column is marked with a dot. In the second row, every other column is marked with a dot. In the third row, every third column is marked with a dot. In general, in the nth row, every nth column is marked with a dot. In this fashion a two-dimensional image is built for all n2 cells. Results of this procedure as generated by computer software are presented in this article. Despite the simplicity of this method, when enough dots are generated, the resulting image turns out to be stunning. This article demonstrates well that computerized visualization can shed new light on old subjects—even those more than 2,000 years old. According to [1] Eratosthenes lived from 276 to 194 BC. Only fragments of Eratosthenes’s original documents have survived. However, a description of his sieve method for finding prime numbers was described in “Introduction to Arithmetic” by Nicomedes written sometime prior to 210 BC [2]. To use the method imagine a written sequence of numbers from 2 to n. Starting at 2 cross off every other number in the sequence except for 2 itself. When done, repeat for 3 (which will be the next remaining number in the sequence) by crossing off every third number. When done, the next number remaining in the sequence will be 5. Repeat the process for every fifth number in the sequence. Continue with this process until you reach the end of the sequence. At the end of the process the numbers remaining in the sequence will be the primes. This simple technique has been used for more than 2,000 years to find prime numbers. One would think that everything there is to know about the method has long since been discovered. Indeed, there are advanced sieve methods and optimization methods. However, these are significant variations of the original method and do not provide any additional characterization of the original method itself. After 2,000 years what more could be said? This article explores the use of computerized visualization to further characterize the Sieve of Eratosthenes. After all, Eratosthenes didn’t have a computer and computer graphics and visualization have only been widely available for the past 20 of those 2,000 years. With a simple extension of the Sieve we arrive at a novel result. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.ams.org/notices/200805/tx080500579p.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
