Divizibilitate / Divizorii unui număr


Editat de Candale Silviu (silviu) la data 2015-08-16
Etichete: nicio etichetă

O problemă frecvent întâlnită este determinarea divizorilor unui număr dat. În practică se pot cere diverse operații cu aceștia: afișarea, însumarea, numărarea, etc.

O primă metodă de determinare a divizorilor constă în a observa că toți divizorii lui n sunt între 1 și n, inclusiv. Putem parcurge numerele din acest interval și verifica dacă sunt într-adevăr divizori ai lui n, caz în care sunt luați în considerare. Următorul program afișează divizorii lui n în acest fel.

#include <iostream>
int main()
{
    int n;
    std :: cin >> n;
    for(int d =1 ; d <= n ; d ++ )
        if(n % d == 0)
            std :: cout << d << " ";
    return 0;
}

De exemplu, pentru n = 24 se va afișa:

1 2 3 4 6 8 12 24 

Programul de mai sus este corect, dar neeficient. Testați-l pentru n = 1.000.000.000 și veți vedea că execuția durează 2-3 secunde. Poate nu pare mult, dar dacă lucrăm cu 1000 de numere cu valori în jurul lui 1.000.000.000, execuția va dura aproximativ 45 de minute – prea mult.

O primă soluție este să observăm că pentru orice n, de la n/2 la n nu mai sunt divizori. Putem astfel să înjumătățim interval în care căutăm divizorii. Astfel înjumătățim și timpul de execuție, dar nu este o îmbunătățire suficientă.

Soluția acceptabilă este să observăm că divizorii oricărui număr n sunt în pereche: dacă d este divizor al lui n, atunci și n/d este divizor al lui n. De exemplu, pentru n = 75.

  • 1 este divizor 75, atunci și 75/1 = 75 este divizor al lui 75;
  • 2 nu este divizor al lui 75
  • 3 este divizor 75, atunci și 75/3 = 25 este divizor al lui 75;
  • 4 nu este divizor al lui 75
  • 5 este divizor 75, atunci și 75/5 = 15 este divizor al lui 75;
  • 6 nu este divizor al lui 75
  • 7 nu este divizor al lui 75
  • 8 nu este divizor al lui 75
  • 9 nu este divizor al lui 75. Mai mult, 9 * 9 > 75, alți divizori nu vom mai găsi.

Divizorii lui 75 sunt: 1 75 3 25 5 15. Constatăm astfel că pentru a determina divizorii lui n este suficient să parcurgem numerele de la 1 la \( \sqrt {n} \).

Un caz special îl constituie pătratele perfecte. În cazul lor trebuie evitată analizarea de două ori a lui \( \sqrt{n} \), care este divizor al lui n. Pentru 36 avem divizorii:

  • 1 în pereche cu 36
  • 2 în pereche cu 18
  • 3 în pereche cu 12
  • 4 în pereche cu 9
  • 5 nu este divizor al lui 36
  • 6 în pereche cu 6. 6 trebuie luat o singură dată!
  • 7*7>36, ne oprim!

Noua variantă a programului care afișează divizorii lui n este:

#include <iostream>
int main()
{
    int n;
    std :: cin >> n;
    for(int d =1 ; d * d <= n ; d ++ )
        if(n % d == 0)
        {
            std :: cout << d << " ";
            if(d * d < n) // dacă d != sqrt(n)
                std :: cout << n / d << " ";
        }
    return 0;
}

În programul de mai sus am evitat utilizarea funcției sqrt, pentru calculul radicalului, prin expresia d <= sqrt(n). Am preferat o formă echivalentă: d * d <= n, mai eficientă!

Fișiere atașate


Vezi și: