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:

Variabilă Valoare
i -12345678910
j (multiplii lui i) -1234567891024681036948510678910
ciur[1] 011
ciur[2] 01122
ciur[3] 01122
ciur[4] 0112233
ciur[5] 01122
ciur[6] 011223344
ciur[7] 01122
ciur[8] 011223344
ciur[9] 0112243
ciur[10] 011223344

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)

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te