Ciurul lui Eratostene în C++

Ce este ciurul lui Eratostene

Ciurul lui Eratostene este un algoritm de determinare a tuturor numerelor prime de la 1 până la o anumită valoare, n. În cadrul problemelor de informatică, ciurul lui Eratostene se poate utiliza atunci când vrem să găsim numere până la 1.000.000 sau 10.000.000, altfel se poate ieși din limitele de spațiu sau de timp.

Cum funcționează algoritmul

Ciurul lui Eratostene funcționează astfel. Să presupunem că vrem să găsim toate numerele prime până la n = 50.

Vom începe prin a scrie numerele de la 2 la 50 (numărul 1 nu contează, deoarece nu este prim).

Vom lua primul număr nemarcat: adică 2. Vom spune că acesta este prim, iar pe toți multiplii săi îi vom marca, deoarece aceștia nu mai pot fi numere prime (fiind multiplu de alt număr).

Căutăm următorul număr nemarcat: 3. Vom spune iar că acesta este prim, iar pe toți multiplii săi îi vom marca. Observăm că unii dintre ei au fost deja marcați anterior, fiind și multipli de 2; acest lucru nu ne încurcă.

Căutăm următorul număr nemarcat: 5. La fel ca și anterior, vom spune că acesta este prim și vom marca multiplii săi, aceștia neputând fi numere prime.

Căutăm următorul număr nemarcat: 7. Acesta este prim și îi marcăm multiplii.

Repetăm procedeul până la final. Tabelul va arăta așa:

Iar numerele nemarcate sunt numerele prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Implementarea ciurului lui Eratostene în C++

Pentru a implementa ciurul lui Eratostene în C++, ne vom folosi de un vector, pe care îl vom numi intuitiv ciur. Lungimea vectorului trebuie să fie cel puțin egală cu numărul de numere pe care vrem să le verificăm: în exemplul anterior, am creat ciurul până la n = 50, așadar vectorul va avea minimum 50 de elemente.

Elementul ciur[i] din ciur va avea una din următoarele valori:

• ciur[i] = 0, dacă numărul i este nemarcat (cu alte cuvinte este prim);
• ciur[i] = 1, dacă numărul i este marcat (cu alte cuvinte nu este prim).

Inițial, toate elementele vectorului vor fi egale cu 0. Vom avansa începând de la 2 până la limita noastră n, iar când găsim un număr nemarcat (prim), îi vom marca toți multiplii săi.

La final, putem afișa pe ecran numerele nemarcate, adică cele prime. Putem de asemenea să ne întrebăm pentru orice număr dacă este sau nu prim, instant.

#include <iostream>

using namespace std;

int ciur[1001]; //Căutăm numerele prime până la 1000

int main()
{
    for(int i = 2; i <= 1000; i++) {
        if(ciur[i] == 0) { //Am găsit un număr nemarcat (prim)
            //Marcăm multiplii lui i
            for(int j = 2 * i; j <= 1000; j += i) {
                ciur[j] = 1;
            }
        }
    }

    //Afișăm pe ecran toate numerele prime găsite
    for(int i = 2; i <= 1000; i++) {
        if(ciur[i] == 0) {
            cout << "Numarul " << i << " este prim\n";
        }
    }
    return 0;
}

Alte aplicații cu ciurul lui Eratostene

Metoda prin care funcționează cirului lui Eratostene poate fi adaptat în rezolvarea altor probleme.

Numărul de divizori al numerelor de la 1 la n

Algoritmul este foarte asemănător. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) //Pentru toate numerele de la 1 la n
        for(int j = i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
            ciur[j]++;

    //Afișăm la final divizorii numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Suma divizorilor numerelor de la 1 la n

Algoritmul adună numărul i în loc să incrementeze cu 1. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) //Pentru toate numerele de la 1 la n
        for(int j = i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
            ciur[j] += i;

    //Afișăm la final suma divizorilor numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Cel mai mic divizor prim al numerelor de la 1 la n

Algoritmul este schimbat, însă nu diferă semnificativ. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                if(ciur[j] == j)
                    ciur[j] = i;
        }

    //Afișăm la final cel mai mic divizor prim al numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Cel mai mare divizor prim al numerelor de la 1 la n

Codul este asemănător cu cel de dinainte. Citește aici explicațiile complete.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                ciur[j] = i;
        }

    //Afișăm la final cel mai mare divizor prim al numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Indicatorul lui Euler al numerelor de la 1 la n

Indicatorul lui Euler este un algoritm foarte util, tratat în această lecție (fără ciur). Pentru explicațiile complete ale algoritmului cu ciur, poți intra pe această lecție.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că numărul de numere prime cu i și mai mici ca acesta este i

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

    //Afișăm la final indicatorul numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Exerciții propuse

Completați următoarele secvențe de cod:

int v[101];
for(int i = 1; i <= ???; i++)
    if(v[i] == 0) {
        for(int j = 2 * i; j <= ???; j++)
            v[j] = 1;
    }

int ciur[100001];
…
if(???[x] == 0) {
    cout << x << " este prim";
} else {
    cout << x << " nu este prim";
}

Alte resurse sau bibliografie

• 100din100: Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
• PbInfo: Ciurul lui Eratostene
• InfoArena: Ciurul lui Eratostene