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. Algoritmul este foarte util, iar în această lecție am văzut cum funcționează și l-am implementat în C++.

În această lecție abordăm alte ciururi derivate din ciurul lui Eratostene. Majoritatea aplicațiilor țin de multiplii sau de divizorii unui număr și au o formă foarte asemănătoare.

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

Algoritmul ia toate numerele de la 1 la n, iar mai apoi toți multiplii lor. Pentru fiecare multiplu în parte, creștem numărul de divizori 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]++;

    //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 ia toate numerele de la 1 la n, iar mai apoi toți multiplii lor. Pentru fiecare multiplu în parte, creștem suma divizorilor cu i. 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 asumă pentru început că răspunsul pentru fiecare număr în parte este chiar el însuși. După aceea, se caută divizorii primi ai fiecăruia și se modifică rezultatele. 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

Algoritmul asumă pentru început că răspunsul pentru fiecare număr în parte este chiar el însuși. După aceea, se caută divizorii primi ai fiecăruia și se modifică rezultatele. 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;
}

Alte resurse sau bibliografie

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