Skip to Content
Article

Sieve of Eratosthenes

In this interactive article, implement the classic Sieve of Eratothenes algorithm for finding prime numbers.

The Sieve of Eratosthenes is one of the oldest-known algorithms, and it’s still helpful for deriving prime numbers! The algorithm is attributed to Eratosthenes, a Greek mathemetician born in the third century BCE.

Eratosthenes

The sieve provides a set of steps for finding all prime numbers up to a given limit. In this article, we’ll cover implementing the Sieve of Eratosthenes in Java. As a reminder, a prime number is a positive number with no divisors but 1 and itself. 2, 3, 11, and 443 are all prime numbers.

Sieve Implementation

The sieve works by first assuming that all numbers from

{2,,n}\{2,\dotsc,n\}

are prime, and then successively marking them as NOT prime.

The algorithm works as follows:

  1. Create a list of all integers from 2 to n.
  2. Start with the smallest number in the list (2, the smallest prime number).
  3. Mark all multiples of that number up to n as not prime.
  4. Move to the next non-marked number and repeat this process until the entire list has been covered.

When the steps are complete, all remaining non-marked numbers are prime.

Example

If we wanted to find all prime numbers less than or equal to 10, we would:

  1. Start with a list where all are assumed to be prime:

    23456789102 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \quad 9 \quad 10
  2. Starting with 2, mark all multiple up to 10 as NOT prime:

    23456789102 \quad 3 \quad \cancel{4} \quad 5 \quad \cancel{6} \quad 7 \quad \cancel{8} \quad 9 \quad \cancel{10}
  3. Move to the next non-marked number, 3, and mark its multiples as NOT prime (6) is already marked:

    23456789102 \quad 3 \quad \cancel{4} \quad 5 \quad \cancel{6} \quad 7 \quad \cancel{8} \quad \cancel{9} \quad \cancel{10}
  4. Continue marking, starting with every non-marked number (in this case, all multiples of 5 are already marked, and 7‘s first multiple is out of range). This means that we have now found all primes up to 10:

    23456789102 \quad 3 \quad \cancel{4} \quad 5 \quad \cancel{6} \quad 7 \quad \cancel{8} \quad \cancel{9} \quad \cancel{10}

This animation shows the whole process for primes from 1 to 100:

Implementation Steps in Java

There are many possible ways of implementing this algorithm in Java. We’ll outline a basic approach here and then walk through it step-by-step.

  1. Create an array of all integers from 2 to n
  2. Set all elements of the array to true
  3. Starting with 2, iterate through the array. If the current element is true, it is still considered prime. Since we know that all multiples of that number are NOT prime, iterate through all multiples of that number up to n and set them equal to false
  4. Change the current element to the next non-false index.
  5. Return the corresponding number value for any element still marked as prime (value of true).

If you’d like to try your hand at implementing the algorithm using these steps, jump to the complete algorithm code block below. Otherwise, we’ll do walk through a step-by-step breakdown below.

Step One: Create the Array

First, we’ll create the array. In this case, we’ll create an array to represent all numbers up to the input limit, but we’ll use the array index to represent the number, and its value (true/false) to represent whether it is prime or not. The original algorithm said to use an array of 2, ..., n, but since we’re using indices to represent the actual number, we’ll start the array from 0 and essentially ignore the values of array[0] and array[1].

For example, after running our sieve, an array representing the primes up to 7 would look like this, with elements at [2], [3], [5], and [7] marked true:

[false, false, true, true, false, true, false, true]

Ready to Learn More?

Find the course that's right for you! Explore our catalog or get a recommendation.