#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/sieve-of-eratosthenes

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/sieve-of-eratosthenes

Repovive

Sieve of Eratosthenes - Algorithm Tutorial | Repovive | Repovive

Repovive.

Back to Algorithms

Sieve of Eratosthenes Algorithm Tutorial

easyMath1 min read1 sections

Learn

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm that finds all prime numbers up to $n$ by iteratively marking multiples of each prime as composite. It runs in $O(n \log \log n)$ time.

You start with $2$ (the first prime) and mark all its multiples. Then you move to the next unmarked number and repeat.

function sieve(n):
    isPrime = array of size n + 1, initialized to true
    isPrime[0] = false
    isPrime[1] = false

    for i from 2 to sqrt(n):
        if isPrime[i]:
            for j from i * i to n, step i:
                isPrime[j] = false

    return isPrime

Starting from : When marking multiples of , you start at because smaller multiples like , , etc. have already been marked by smaller primes.

Practice this Algorithm

Apply what you learned by solving the practice problem for Sieve of Eratosthenes.

Go to Practice Problem

Related Algorithms

Combinations (nCr mod p)