Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Resources/Math/Eratosten elagi

Eratosten elagi

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

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESAlmost Prime

CODEFORCESNoldbach problem

CODEFORCESSherlock and his girlfriend

CODEFORCESColliders

ATCODERD. AABCC

ATCODERD. Not Divisible

ATCODERD. 250-like Number

ATCODERE. Coprime

Eratosten elagi - Resources

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) {
    ...
}