Cati divizori are un numar?

0 Comments

problemele interesante

Ne punem problema cum se determina divizorii unui numar dat si cati divizori are un numar dat?

Prima problema care iti cer sa o abordezi aici este de a stabili care sunt divizorii unui numar nr citit de la tastatura.
De exemplu 24 are divizorii 1, 2, 3, 4, 6, 8, 12, 24.
Ar trebui sa parcurgi tot intervalul de valori de la 1 la `nr` ca sa gasesti toate aceste numere.
Daca observi insa ca aceste numere apar in pereche, deci daca parcurgi numai pana la jumatate intervalul si gasesti un divizor `d`, atunci sigur si `nr/d` va fi un divizor.
Optimizeaza si mai mult si cauta numai pana la parte intreaga din radical din numar. Daca nu gasesti pana acolo un divizor, nu vei gasi nici mai departe.
Divizorii unui numar
Divizorii unui numar

Algoritmul in pseudocod este:

ALGORITM DIVIZORI ESTE:
    CITESTE nr;
    PENTRU (d=1; d*d<n; d++)  EXECUTA:
        DACA (nr % d == 0)  ATUNCI
            TIPARESTE nr, nr / d;
        SFARSIT_DACA;
    SFARSIT_PENTRU.
SFARSIT_ALGORITM.

 

Un caz particular il reprezinta patratele perfecte.
De exemplu 64, are divizorii 1, 2, 4, 8, 16, 32, 64.
Deci 8 este pereche cu 8 si nu il pot scrie sau numara de 2 ori.
Algoritmul trebuie completat in acest caz pentru a tipari si `sqrt(nr)`.
ALGORITM DIVIZORI ESTE:
    CITESTE nr;
    PENTRU (d=1; d*d<n; d++)  EXECUTA:
        DACA (nr % d == 0)  ATUNCI
            TIPARESTE nr, nr / d;
        SFARSIT_DACA.
    SFARSIT_PENTRU.
    DACA (d*d == nr) ATUNCI
            TIPARESTE d;
        SFARSIT_DACA.
SFARSIT_ALGORITM.
O a doua problema care ti-o supun atentiei se refera la a numara cati divizori are un numar dat nr?
Daca analizezi vei vedea rapid ca diferenta consta in faptul ca nu iti mai cer ca algoritmul sa tipareasca divizorii ci sa ii numere.

Algoritmul in pseudocod este:

ALGORITM DIVIZORI ESTE:
    CITESTE nr;
    contor = 0;
    PENTRU (d=1;  d*d<n;  d++)  EXECUTA:
        DACA (nr % d == 0)  ATUNCI
            contor + = 2;
        SFARSIT_DACA.
    SFARSIT_PENTRU.
    DACA (d*d == nr) ATUNCI
            contor++;
    SFARSIT_DACA.
    TIPARESTE contor;
SFARSIT_ALGORITM.
Ca aplicatii la acest subiect poti aborda:
– suma / produsul divizorilor unui numar;
– suma / produsul divizorilor pari / impari ai unui numar.
Etichete: , , , , , , , , , , , , , , , , , ,