The Sieve of Eratosthenes

-

A sieve is a superb metaphor for this algorithm (Source)

Much like a sieve, this algorithm starts with assuming all numbers are primes, then slowly “sifts” through them to discover the true primes. Let’s walk through the algorithm using a basic example for locating all primes between two and ten. To make use of the sieve, we ignore the primary and begin with two. We start by assuming every number is prime, like below

Our starting list of primes.

Next, we move from left to right. Starting with two, we now cross off every multiple of two (besides two itself). This crossing off signifies that these numbers will not be prime, since they will be divided by two. Do that for each number within the list to get the next result:

We’ve cancelled all multiples of two.

Now, we move to the best by one number to get to 3. Identical to we did for multiples of two, we now cancel all multiples of three. For optimum efficiency, we don’t consider 3*2 because we already know multiples of two have been cancelled.

We’ve cancelled all multiples of three.

Next down the list is 4 which has already been crossed out. When the sieve gets to a number already removed, it skips to the subsequent one. Moving down the list we now have to cancel multiples of 5 and 7, but there aren’t any left. Our list now only has prime numbers remaining! That is the fundamental approach to the sieve, and will be expanded for much larger lists of numbers. To see this method implemented into Python, take a look at this page.

ASK ANA

What are your thoughts on this topic?
Let us know in the comments below.

0 0 votes
Article Rating
guest
0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Share this article

Recent posts

0
Would love your thoughts, please comment.x
()
x