Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)

Dându-se un număr natural n, să se afișeze pe ecran numărul de divizori al tuturor numerelor de la 1 la n.

Exemplu. Pentru n = 10, răspunsul este 1 2 2 3 2 4 2 4 3 4 (1 are 1 divizor, 2 are 2 divizori, 3 are 2 divizori, etc.).

Vom prezenta două metode, prima naivă și a doua folosind Ciurul lui Eratostene, modificat.

Metoda 1 (naivă)

O primă metodă constă în parcurgerea tuturor numerelor de la 1 la n și aflarea, folosind algoritmul de determinare a numărului de divizori, numărul divizorilor numărului curent.

Algoritmul este destul de intuitiv, însă nu este îndeajuns de eficient.

Implementare C++

#include <iostream>

using namespace std;

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

    //Parcurgem toate numerele de la 1 la n și determinăm divizorii fiecăruia
    //Mai multe detalii găsiți mai sus
    for(int i = 1; i <= n; i++) {
        int nrDiv = 0; //Numărul de divizori al numărului curent
        for(int d = 1; d * d <= i; d++) {
            if(i % d == 0) { //Am găsit un divizor
                nrDiv++;
                if(d != i / d) { //Perechea divizorului diferă de numărul în sine
                    nrDiv++;
                }
            }
        }
        cout << nrDiv << " ";
    }
    return 0;
}

Metoda 2 (ciurul lui Eratostene)

Ciurul lui Eratostene este un algoritm important care ia numeroase forme, însă la bază poate să determine pentru orice număr de la 1 la n, care sunt prime. Această lecție explică în detaliu cum funcționează algoritmul de bază.

Putem să adaptăm un pic algoritmul: pentru numărul curent i, vom aduna cu 1 numărul de divizori ai tuturor multiplilor lui i: i, 2 * i, 3 * i, ….

Practic, metoda aceasta, în loc să caute divizorii fiecărui număr (ca și în prima soluție), caută pentru fiecare număr multiplii acestuia, pe care îi marchează.

Vizualizarea algoritmului (animație)

Iată un exemplu, pentru n = 10:

Implementare în C++

#include <iostream>

using namespace std;

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

    //Ne declarăm ciurul
    int ciur[1001];
    for(int i = 1; i <= n; i++) //Golim șirul
        ciur[i] = 0;
    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;
}

Bibliografie sau alte resurse

• PbInfo (algoritmi ciurul lui Eratostene)
• 100din100 (lecție completă)
• PbInfo (algoritmul de bază de ciur)