Sieve of Eratosthenes Algorithm

Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so (Ref Wiki).

Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthene’s method: When the algorithm terminates, all the numbers in the list that are not marked are prime.

Explanation with Example:

Let us take an example when n = 100. So, we need to print all prime numbers smaller than or equal to 100.

We create a list of all numbers from 2 to 100

According to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it.

Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it.

We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it.

We move to our next unmarked number 7 and mark all multiples of 7 and are greater than or equal to the square of it.

We continue this process, and our final table will look like below:

Pseudocode

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially, all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

Leetcode problem

Loading...LeetCode