Sieve of Eratosthenes

DSA · Classic Algorithms

Theory

The Sieve of Eratosthenes finds all prime numbers up to a limit n efficiently. It starts with a list marking every number from 2 to n as possibly prime. It takes the first unmarked number, 2, and crosses out all its multiples; then it moves to the next unmarked number, 3, and crosses out its multiples, and so on. You only need to start crossing out from p * p, because smaller multiples were already removed by smaller primes, and you can stop once p * p exceeds n. Whatever remains unmarked is prime. The sieve runs in O(n log log n) time, which is almost linear, compared with O(n * sqrt(n)) for testing each number separately. Its main limit is memory: it needs one flag per number up to n.

Why we use it

Prime generation is common in number theory problems, hashing, cryptography exercises and competitive programming. The sieve is dramatically faster than trial division when many primes are needed.

When to use it

Use it when you need all primes (or prime checks) up to a limit of a few tens of millions. For a single large number, use a primality test instead.

How it works

  1. Mark 2..n as prime
  2. p = 2
  3. p * p <= n? Yes: If p is prime, cross out p*p, p*p+p, .... No: Stop.
  4. p = p + 1, repeat
  5. Unmarked numbers are prime

Syntax

is_prime = [True] * (n + 1)
for p in 2..sqrt(n):
    if is_prime[p]: mark p*p, p*p+p, ... as False
Time O(n log log n)   Space O(n)

Example

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i, flag in enumerate(is_prime) if flag]

print("Primes up to 50:", sieve(50))
primes = sieve(1_000_000)
print("Number of primes below 1 million:", len(primes))
print("Largest:", primes[-1])

# Smallest prime factor sieve for fast factorisation
def spf_sieve(n):
    spf = list(range(n + 1))
    for p in range(2, int(n ** 0.5) + 1):
        if spf[p] == p:
            for m in range(p * p, n + 1, p):
                if spf[m] == m:
                    spf[m] = p
    return spf
spf = spf_sieve(1000)
x, factors = 360, []
while x > 1:
    factors.append(spf[x]); x //= spf[x]
print("360 =", " x ".join(map(str, factors)))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic