Module 1: Scanline

Scanline / Event Processing

Module 2: Introduction to DP

Introduction to Dynamic Programming

Module 3: Number theory

Prime numbers and factorization
Sieve of Eratosthenes

Module 4: Graph traversals

Depth-First Search (DFS)
Breadth-First Search (BFS)
Bipartiteness check
Finding connected components
Topological sorting

Module 5: Shortest paths

Dijkstra's algorithm
Floyd–Warshall Algorithm
Bellman–Ford algorithm

Module 6: Game Theory - Basics

Basics of Game States

Module 7: Introduction to Geometry

Signed area of a triangle
Basic Geometry
Bonus Geometry Problems

Module 8: Various types of Binary Search

Binary search by answer
Binary search on a real-valued answer
Ternary search
Binary search by powers of two

Sieve of Eratosthenes - Preparation to IOI Part 2

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 2/Module 3: Number theory/Sieve of Eratosthenes

Sieve of Eratosthenes

Learn about sieve of Eratosthenes

Introduction

We are given the range of numbers $[1, \ldots, N]$ , and we need to find all prime numbers in this range.

For example, in the range

[1, 2, 3, \ldots, 12]

the prime numbers are:

2, 3, 5, 7, 11

5

,

7

,

11

The classical algorithm for this task is the Sieve of Eratosthenes.

Idea

Observation 1

While processing numbers in the range, we can immediately mark all multiples of the current prime number as composite.

For example:

when we process 2, we can mark all multiples of 2 as composite;
when we process 3, we can mark all multiples of 3 as composite;
and so on.

This allows us to gradually remove all non-prime numbers.

Sieve of Eratosthenes — illustration

Observation 2

Recall an important fact: if a number $N$ is composite, then it has a prime divisor not greater than $\sqrt{N}$ .

Therefore, to find all primes up to $N$ , it is enough to perform the sieving process only with numbers up to $\sqrt{N}$ .

Algorithm

We create an array prime, where:

prime[x] = true means that x is currently considered prime;
prime[x] = false means that x is composite.

Initially, all numbers are marked as prime except 0 and 1.

Then for each number i from 2 to $\sqrt{N}$ :

if i is still marked as prime, then mark all multiples of i as composite.

Notes

1. Why do we start from $i^2$ ?

The inner loop starts from $i^2$ , because all smaller multiples of $i$ have already been processed earlier.

For example, if we are at i = 5, then:

10 = 2 \cdot 5 has already been marked when processing 2;
15 = 3 \cdot 5 has already been marked when processing 3;
20 = 4 \cdot 5 has already been marked even earlier.

So the first new multiple we need to mark is $5^2 = 25$ .

2. About overflow

In some problems, the value $i^2$ may overflow the int type.

In such cases, it is safer to cast i to long long before multiplication.

For example:

int n;
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;

for (int i = 2; i * i <= n; ++i) {
    if (prime[i]) {
        for (int j = i * i; j <= n; j += i) {
            prime[j] = false;
        }
    }
}

for (int i = 2; 1LL * i * i <= n; ++i) {
    ...
}