Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Sieve of Eratosthenes

Sieve of Eratosthenes is used to find prime numbers up to some predefined integer n. For sure, we can just test all the numbers in range from 2 to n for primality using some approach, but it is quite inefficient. Sieve of Eratosthenes is a simple algorithm to find prime numbers. Though, there are better algorithms exist today, sieve of Eratosthenes is a great example of the sieve approach.

Algorithm

First of all algorithm requires a bit array isComposite to store n - 1 numbers: isComposite[2 .. n]. Initially the array contains zeros in all cells. During algorithm's work, numbers, which can be represented as k * p, where k ≥ 2, p is prime, are marked as composite numbers by writing 1 in a corresponding cell. Algorithm consists of two nested loops: outer, seeking for unmarked numbers (primes), and inner, marking primes' multiples as composites.

  • For all numbers m: 2 .. n, if m is unmarked:
    • add m to primes list;
    • mark all it's multiples, lesser or equal, than n (k * m ≤ n, k ≥ 2);
  • otherwise, if m is marked, then it is a composite number.

Modification

Let's notice, that algorithm can start marking multiples beginning from square of a found unmarked number. Indeed,

For m = 2, algorithm marks

	2 * 2   3 * 2   4 * 2   5 * 2   6 * 2   7 * 2   ...

For m = 3,

	2 * 3

were already marked on m = 2 step.

For m = 5,

	2 * 5   3 * 5   4 * 5 (= 10 * 2)

were already marked on m = 2 and m = 3 steps.

Strong proof is omitted, but you can easily prove it on your own. Modified algorithm is as following:

  • For all numbers m: 2 .. √n, if m is unmarked:
    • add m to primes list;
    • mark all it's multiples, starting from square, lesser or equal than n (k * m ≤ n, k ≥ m);
  • otherwise, if m is marked, then it is a composite number;
  • check all numbers in range √n .. n. All found unmarked numbers are primes, add them to list.

Example

Apply sieve of Eratosthenes to find all primes in range 2..100.

Initial grid

Sieve of Eratosthenes example, initial grid

2 is prime, mark all multiples of 2, starting from 4

Sieve of Eratosthenes example, 2 is prime, mark all multiples of 2

3 is prime, mark all multiples of 3, starting from 9

Sieve of Eratosthenes example, 3 is prime, mark all multiples of 3, starting from 9

5 is prime, mark all multiples of 5, starting from 25

Sieve of Eratosthenes example, 5 is prime, mark all multiples of 5, starting from 25

7 is prime, mark all multiples of 7, starting from 49

Sieve of Eratosthenes example, 7 is prime, mark all multiples of 7, starting from 49

112 is more, than 100, all unmarked numbers are primes

Sieve of Eratosthenes example, 11^2 is more, than 100, all unmarked numbers are primes

Final result

Sieve of Eratosthenes example, final result

Complexity analysis

Computational complexity of the algorithm is O(nlog(log(n))). Strong proof of this fact is not too complex and based on several approximations from the prime numbers' theory. It can be found in [1]. The space complexity is O(n). Actually, on the modern hardware, algorithm will run out of memory much faster, than it would run out of time.

Code snippets

Java implementation

public void runEratosthenesSieve(int upperBound) {

      int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

      boolean[] isComposite = new boolean[upperBound + 1];

      for (int m = 2; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                  System.out.print(m + " ");

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite[k] = true;

            }

      }

      for (int m = upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite[m])

                  System.out.print(m + " ");

}

C++ implementation

void runEratosthenesSieve(int upperBound) {

      int upperBoundSquareRoot = (int)sqrt((double)upperBound);

      bool *isComposite = new bool[upperBound + 1];

      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));

      for (int m = 2; m <= upperBoundSquareRoot; m++) {

            if (!isComposite[m]) {

                  cout << m << " ";

                  for (int k = m * m; k <= upperBound; k += m)

                        isComposite[k] = true;

            }

      }

      for (int m = upperBoundSquareRoot; m <= upperBound; m++)

            if (!isComposite[m])

                  cout << m << " ";

      delete [] isComposite;

}

Recommended books

  1. Victor Shoup. A Computational Introduction to Number Theory and Algebra.
  2. Peter J. Giblin. Primes and Programming.
  3. David M. Bressoud. Factorization and Primality Testing.
  4. Hans Riesel. Prime Numbers and Computer Methods for Factorization.

Visualizers

  1. Sieve of Eratosthenes applet
  2. Sieve of Eratosthenes animation by Philip Dorrell (JavaScript)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Partners Ads        aquarium filter        drawing storage        

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: