Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)

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

Exemplu. Pentru n = 10, răspunsul este 1 3 4 7 6 12 8 15 13 18 (1 are suma divizorilor 1, 2 are suma divizorilor 1 + 2 = 3, etc.).

Vom prezenta două metode, prima naivă și a doua folosind un algoritm similar cu cel de la Ciurul lui Eratostene.

Metoda 1 (naivă)

O primă metodă constă în parcurgerea tuturor numerelor de la 1 la n și aflarea, folosind algoritmul de determinare a sumei divizorilor, suma 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 sumDiv = 0; //Suma divizorilor al numărului curent
        for(int d = 1; d * d <= i; d++) {
            if(i % d == 0) { //Am găsit un divizor
                sumDiv += d;
                if(d != i / d) { //Perechea divizorului diferă de numărul în sine
                    sumDiv += i / d;
                }
            }
        }
        cout << sumDiv << " ";
    }
    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 ciurului lui Eratostene.

Putem să adaptăm un pic algoritmul: pentru numărul curent i, vom lua toți multiplii săi j, iar suma divizorilor numărului j crește cu i.

Implementare C++

#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;
}

Alte resurse sau bibliografie

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