Sieve of Eratosthenes

Jai Ganesh · 2021-12-07 15:47:17

Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

The earliest known reference to the sieve is in Nicomachus of Gerasa's Introduction to Arithmetic, an early 2nd cent. CE book, which describes it and attributes it to Eratosthenes of Cyrene, a 3rd cent. BCE Greek mathematician.

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.

Overview

A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

* Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
* Initially, let p equal 2, the smallest prime number.
* Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
* Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
* When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

The main idea here is that every value given to p will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).

As a refinement, it is sufficient to mark the numbers in step 3 starting from p^2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p^2 is greater than n.

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count in increments of 2p from p^2 in step 3, thus marking only odd multiples of p. This actually appears in the original algorithm. This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of p are generated that are coprime with those small primes, in the first place.

Example

To find all the prime numbers less than or equal to 30, proceed as follows.

First, generate a list of integers from 2 to 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. The numbers not crossed out at this point in the list are all the prime numbers below 30:

2 3 5 7 11 13 17 19 23 29

Given below is a photograph of all prime numbers from 1 to 100 highlighted in yellow color:

The polymath

Eratosthenes of Cyrene (c. 276 BC – c. 195/194 BC) was a Greek polymath: a mathematician, geographer, poet, astronomer, and music theorist. He was a man of learning, becoming the chief librarian at the Library of Alexandria. His work is comparable to what is now known as the study of geography, and he introduced some of the terminology still used today.

He is best known for being the first person known to calculate the circumference of the Earth, which he did by using the extensive survey results he could access in his role at the Library; his calculation was remarkably accurate. He was also the first to calculate Earth's axial tilt, which also proved to have remarkable accuracy. He created the first global projection of the world, incorporating parallels and meridians based on the available geographic knowledge of his era.

Eratosthenes was the founder of scientific chronology; he endeavoured to revise the dates of the main events of the semi-mythological Trojan War, dating the Sack of Troy to 1183 BC. In number theory, he introduced the sieve of Eratosthenes, an efficient method of identifying prime numbers.

He was a figure of influence in many fields. According to an entry in the Suda (a 10th-century encyclopedia), his critics scorned him, calling him Beta (the second letter of the Greek alphabet) because he always came in second in all his endeavours. Nonetheless, his devotees nicknamed him Pentathlos after the Olympians who were well rounded competitors, for he had proven himself to be knowledgeable in every area of learning. Eratosthenes yearned to understand the complexities of the entire world.

Biography

Eratosthenes (c.276 to 194 B.C.), a mathematician, is known for his mathematical calculations and geometry.

Eratosthenes was called "Beta" (the second letter of the Greek alphabet) because he was never first, but he is more famous than his "Alpha" teachers because his discoveries are still used today. Chief among these is the calculation of the circumference of the earth and the development of a mathematical sieve named after him. He made a calendar with leap years, a 675-star catalog, and maps. He recognized the Nile's source was a lake, and that rains in the lake region caused the Nile to flood.

Eratosthenes: Life and Career Facts

Eratosthenes was the third librarian at the famous Library of Alexandria. He studied under the Stoic philosopher Zeno, Ariston, Lysanias, and the poet-philosopher Callimachus. Eratosthenes wrote a Geographica based on his calculations of the circumference of the earth.

Writing of Eratosthenes

Much of what Eratosthenes wrote is now lost, including a geometrical treatise, On Means, and one on the mathematics behind Plato's philosophy, Platonicus. He also wrote the fundamentals of astronomy in a poem called Hermes. His most famous calculation, in the now lost treatise On the Measurement of the Earth, explains how he compared the shadow of the sun at Summer Solstice noon in two places, Alexandria and Syene.

Eratosthenes Calculates the Circumference of the Earth

By comparing the shadow of the sun at Summer Solstice noon at Alexandria and Syene, and knowing the distance between the two, Eratosthenes calculated the circumference of the earth. The sun shone directly into a well at Syene at noon. At Alexandria, the angle of inclination of the sun was about 7 degrees. With this information, and knowing that Syene was 787 km due south of Alexandrian Eratosthenes calculated the circumference of the earth to be 250,000 stadia (about 24,662 miles).

Summary

Eratosthenes of Cyrene (c. 276 BC – c. 195/194 BC) was a Greek polymath: a mathematician, geographer, poet, astronomer, and music theorist. He was a man of learning, becoming the chief librarian at the Library of Alexandria. His work is comparable to what is now known as the study of geography, and he introduced some of the terminology still used today.

He is best known for being the first person known to calculate the circumference of the Earth, which he did by using the extensive survey results he could access in his role at the Library; his calculation was remarkably accurate. He was also the first to calculate Earth's axial tilt, which also proved to have remarkable accuracy. He created the first global projection of the world, incorporating parallels and meridians based on the available geographic knowledge of his era.

Eratosthenes was the founder of scientific chronology; he endeavoured to revise the dates of the main events of the semi-mythological Trojan War, dating the Sack of Troy to 1183 BC. In number theory, he introduced the sieve of Eratosthenes, an efficient method of identifying prime numbers.

He was a figure of influence in many fields. According to an entry in the Suda (a 10th-century encyclopedia), his critics scorned him, calling him Beta (the second letter of the Greek alphabet) because he always came in second in all his endeavours. Nonetheless, his devotees nicknamed him Pentathlos after the Olympians who were well rounded competitors, for he had proven himself to be knowledgeable in every area of learning. Eratosthenes yearned to understand the complexities of the entire world.

(The Suda or Souda is a large 10th-century Byzantine encyclopedia of the ancient Mediterranean world, formerly attributed to an author called Soudas or Souidas. It is an encyclopedic lexicon, written in Greek, with 30,000 entries, many drawing from ancient sources that have since been lost, and often derived from medieval Christian compilers.)

Math Is Fun Forum

#1 2021-12-07 15:47:17

Sieve of Eratosthenes

Board footer