Ciurul lui Eratostene

Am învățat deja să verificăm dacă un număr este prim, testând dacă are vreun divizor de la 2 până la sqrt(n).

Dar dacă vrem să aflăm toate numerele prime până la o limită n? Să verificăm fiecare număr individual ar fi lent.

Există o metodă mult mai rapidă, inventată în urmă cu peste 2000 de ani: Ciurul lui Eratostene.

Ideea

Imaginează-ți că scrii pe o foaie toate numerele de la 2 la n. Apoi:

1. Începi cu 2 (primul număr prim).
2. Tai toți multiplii lui 2 (4, 6, 8, 10, …) - nu sunt primi.
3. Treci la următorul număr netăiat: 3. E prim.
4. Tai toți multiplii lui 3 (6, 9, 12, 15, …).
5. Treci la următorul netăiat: 5. E prim.
6. Tai multiplii lui 5.
7. Continui până la n.

La final, numerele care au rămas netăiate sunt exact numerele prime.

Exemplu vizual pentru n = 30

Numerele de la 2 la 30:

 2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

Pasul 1: tăiem multiplii lui 2

 2  3  x  5  x  7  x  9  x
11  x 13  x 15  x 17  x 19  x
21  x 23  x 25  x 27  x 29  x

Pasul 2: tăiem multiplii lui 3

 2  3  x  5  x  7  x  x  x
11  x 13  x  x  x 17  x 19  x
 x  x 23  x 25  x  x  x 29  x

Pasul 3: tăiem multiplii lui 5

 2  3  x  5  x  7  x  x  x
11  x 13  x  x  x 17  x 19  x
 x  x 23  x  x  x  x  x 29  x

Numerele rămase sunt prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Implementarea cu vector

Folosim un vector ciur unde: - ciur[x] = 0 înseamnă că x este prim (netăiat) - ciur[x] = 1 înseamnă că x nu este prim (tăiat)

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int ciur[1000001]; // 0 = prim, 1 = nu e prim
int n;

int main()
{
    fin >> n;

    ciur[0] = 1; // 0 nu e prim
    ciur[1] = 1; // 1 nu e prim

    for (int i = 2; i * i <= n; i++) {
        if (ciur[i] == 0) {
            // i este prim - taiem toti multiplii lui
            for (int j = i * i; j <= n; j = j + i) {
                ciur[j] = 1;
            }
        }
    }

    // Afișăm numerele prime
    for (int i = 2; i <= n; i++) {
        if (ciur[i] == 0) {
            fout << i << " ";
        }
    }

    return 0;
}

date.in:

30

date.out:

2 3 5 7 11 13 17 19 23 29

Explicația codului pas cu pas

De ce i * i <= n?

Dacă i * i > n, toți multiplii lui i mai mici decât n au fost deja tăiați de numere mai mici.

De exemplu, pentru n = 30: verificăm doar i = 2, 3, 4, 5 (pentru că 6 * 6 = 36 > 30).

De ce începem tăierea de la i * i?

Multiplii lui i mai mici decât i * i au fost deja tăiați de factori mai mici.

De exemplu, pentru i = 5: - 5 * 2 = 10 - deja tăiat de 2 - 5 * 3 = 15 - deja tăiat de 3 - 5 * 4 = 20 - deja tăiat de 2 - 5 * 5 = 25 - primul multiplu nou, de aici începem

Tabel pas cu pas pentru n = 20

Ne oprim: 5 * 5 = 25 > 20.

Numerele prime până la 20: 2, 3, 5, 7, 11, 13, 17, 19.

Problema 1: câte numere prime sunt până la n?

int cnt = 0;

for (int i = 2; i <= n; i++) {
    if (ciur[i] == 0) {
        cnt++;
    }
}

fout << cnt;

Problema 2: al k-lea număr prim

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int ciur[1000001];

int main()
{
    int n = 1000000; // limita superioara
    int k;
    fin >> k;

    ciur[0] = 1;
    ciur[1] = 1;

    for (int i = 2; i * i <= n; i++) {
        if (ciur[i] == 0) {
            for (int j = i * i; j <= n; j = j + i) {
                ciur[j] = 1;
            }
        }
    }

    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (ciur[i] == 0) {
            cnt++;
            if (cnt == k) {
                fout << i;
                return 0;
            }
        }
    }

    return 0;
}

date.in:

10

date.out:

29

Al 10-lea număr prim este 29.

Problema 3: descompunerea în factori primi

Cu ciurul deja construit, putem descompune un număr în factori primi foarte rapid:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int ciur[1000001];

int main()
{
    int n;
    fin >> n;

    // Construim ciurul
    ciur[0] = 1;
    ciur[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (ciur[i] == 0) {
            for (int j = i * i; j <= n; j = j + i) {
                ciur[j] = 1;
            }
        }
    }

    // Descompunem n in factori primi
    for (int d = 2; d <= n; d++) {
        if (ciur[d] == 1) continue; // d nu e prim, sarim

        int putere = 0;
        while (n % d == 0) {
            putere++;
            n = n / d;
        }

        if (putere > 0) {
            fout << d << "^" << putere << " ";
        }
    }

    return 0;
}

date.in:

360

date.out:

2^3 3^2 5^1

Explicație: 360 = 2^3 * 3^2 * 5^1 = 8 * 9 * 5.

Problema 4: suma divizorilor primi ai unui număr

int suma = 0;

for (int d = 2; d <= n; d++) {
    if (ciur[d] == 0 && n % d == 0) {
        suma = suma + d;
    }
}

fout << suma;

Exemplu: n = 12, divizorii primi: 2, 3. Suma: 5.

De ce este rapid ciurul?

Comparație cu verificarea individuală:

Pentru un milion de numere, ciurul este de 250 de ori mai rapid!

Greșeli frecvente

1. Uitarea marcării lui 0 și 1

// GRESIT: 0 si 1 raman "prime"
// CORECT:
ciur[0] = 1;
ciur[1] = 1;

0 și 1 nu sunt numere prime.

2. Bucla exterioară merge până la n în loc de sqrt(n)

// INEFICIENT:
for (int i = 2; i <= n; i++) {

// EFICIENT:
for (int i = 2; i * i <= n; i++) {

Ambele dau același rezultat, dar varianta cu i * i <= n este mult mai rapidă.

3. Tăierea începe de la 2 * i în loc de i * i

// FUNCTIONEAZA dar e mai lent:
for (int j = 2 * i; j <= n; j = j + i) {

// OPTIMIZAT:
for (int j = i * i; j <= n; j = j + i) {

Ambele sunt corecte, dar i * i evită tăieri deja făcute.

4. Vectorul prea mic

Dacă n poate fi 1.000.000, vectorul trebuie să fie ciur[1000001].

5. Confuzia: ciur[x] == 0 înseamnă prim

În ciur, 0 = prim (netăiat), 1 = nu e prim (tăiat). E invers față de ce ai aștepta intuitiv.

Poți folosi și convenția inversă (1 = prim), dar aceasta e cea standard.

Ce să reții

• Ciurul lui Eratostene găsește toate numerele prime până la n foarte eficient.
• Ideea: tăiem toți multiplii fiecărui număr prim.
• ciur[x] = 0 înseamnă că x este prim.
• Bucla exterioară merge până la sqrt(n) (i * i <= n).
• Tăierea multiplilor începe de la i * i.
• Este mult mai rapid decât verificarea individuală.
• Aplicații: numărare prime, al k-lea prim, descompunere în factori.
• Vectorul trebuie declarat global și suficient de mare.

Probleme

pbinfoEratostene→

pbinfoEratostene2→

pbinfoExtraprime→

pbinfoFantastice→