În acest articol vom prezenta 3 aplicații ale descompunerii numerelor în factori primi interesante ce vor face rezolvarea unor anumite cerințe din problemele de informatică mult mai ușoară, dar și eficientă din punct de vedere al timpului și memoriei.

Determinarea numărului de divizori ai unui număr

O prima metodă de aflare a numărului de divizori ai unui număr dat n este parcurgerea intervalului \([2,\frac{n}{2}]\) numărând valorile ce reprezintă un divizor pentru numărul n.

O soluție mult mai eficientă constă în folosirea următoarei propietăți. Vom folosi ca notații:

\(p\) – factorul prim
\(e\) – exponentul factorului prim.

 Pentru numărul n ce are descompunerea în factori \(n={p_1}^{e_1}\cdot{p_2}^{e_2}\cdot…….\cdot{p_k}^{e_k}\),numărul de divizori poate fi calculat utilizând formula: \(({e_1}+1)\cdot({e_2}+1)\cdot…….\cdot({e_k}+1)\)

Să luăm ca exemplu numărul 36. Descompunerea în factori primi a acestuia este: \(36=2^2\cdot3^2\)

Divizorii acestuia sunt: \({1,2,3,4,6,9,12,18,36}\) – 9 divizori.

Aplicăm propietatea de mai sus. Luăm exponentul primului factor prim. Adunăm cu 1 și înmulțim cu exponentul următorului având grijă ca acesta să fie adunat tot cu 1.

\(D_{36}=(2+1)\cdot(2+1)\)
\(D_{36}=3\cdot3\)
\(D_{36}=9\) => Obținem că numărul 36 are 9 divizori.

O implementare în C++:

int nrDiv(int a)
{
    /*
    In e stocam exponentul factorului prim pe care il parcurgem
    d - Reprezinta factorul prim gasit
    rez - Rezultatul final */
    int e,d,rez;
    e=0; // Initializam exponentul cu 0
    while(a%2==0) //Luam cazul special: singurul numar prim par este 2.
    {
        a/=2;
        e++;
    }
    /*Initializam rezultatul cu primul exponent gasit.
    Chiar daca exista sansa ca 2 sa nu fie factor prim al numarului
    caruia dorim sa ii gasim numarul divizorilor rezultatul tot este initializat
    cu 1 fiindca exponentul este initializat cu 0.

    */
    rez=e+1;
    d=3; //Urmatorul nr. prim este 3.
    while(a>1 && d*d<=a) //Parcurgem intervalul [2, radical(n)]
    {
        e=0;
        while(a%d==0)
        {
            a/=d;
            e++;
        }
        //Inmultim la rezultat exponentul gasit.
        //Nu uitam sa fie adunat cu 1.
        rez*=(e+1);
        d+=2;
    }
    if(a>1)
        rez*=2;
    return rez; //Final.
}

Suma divizorilor unui număr

O soluție reprezintă determinarea divizorilor în mod asemănător ca mai sus, însă adunăm divizorii într-o variabilă.

Pentru a afla mult mai repede suma divizorilor unui număr vom folosi următoarea propietate:

 Pentru numărul n ce are descompunerea în factori \(n={p_1}^{e_1}\cdot{p_2}^{e_2}…….\cdot{p_k}^{e_k}\),suma divizorilor poate fi calculată utilizând formula: \(\frac{{p_1}^{{e_1}+1}-1}{{p_1}-1}\cdot\frac{{p_2}^{{e_2}+1}-1}{{p_2}-1}\cdot…….\cdot\frac{{p_k}^{{e_k}+1}-1}{{p_k}-1}\)

Să luăm ca exemplu tot numărul 36. Știm că descompunerea acestuia în factori primi este \(36=2^2*3^2\). Divizorii acestuia sunt: \({1,2,3,4,6,9,12,18,36}\)-suma acestora este 91.

Acum să aplicăm propietatea enunțată mai sus:

\(S_{36}=\frac{2^{(2+1)}-1}{2-1}\cdot\frac{3^{(2+1)}-1}{3-1}\)
\(S_{36}=\frac{2^3-1}{1}\cdot\frac{3^3-1}{2}\)
\(S_{36}=7\cdot\frac{26}{2}\)
\(S_{36}=7\cdot13\)
\(S_{36}=91\) => Suma divizorilor numărului 36 este 91.

O implementare în C++:

int SumDiv(int n)
{
    int e,p,d;
    e=1;
    p=1;
    while(n%2==0)
    {
        n/=2;
        e*=2;
    }
    e*=2;
    e--;
    p=e;
    for(d=3; n>1 && d*d<=n; d+=2)
    {
        e=1;
        while(n%d==0)
        {
            n/=d;
            e*=d;
        }
        e*=d;
        e--;
        e=e/(d-1);
        p*=e;
    }
    if(n>1)
        p*=(1+n);
    return p;
}

Indicatorul Euler

Indicatorul Euler sau funcția totent determină numărul de valori mai mici sau egale cu un număr dat și prime cu acesta. Aceasta se notează \(\phi(n)\) și se poate afla aplicând următoarea propietate:

 Pentru numărul n ce are descompunerea în factori \(n={p_1}^{e_1}\cdot{p_2}^{e_2}…….\cdot{p_k}^{e_k}\), indicatorul Euler se poate afla utilizând următoarea formulă: \(\phi(n)=n\cdot(1-\frac{1}{{p_1}})\cdot(1-\frac{1}{{p_2}})\cdot……\cdot(1-\frac{1}{{p_k}})\)

Să luăm ca exemplu numărul 9. Acesta are descompunerea în factori primi \(9=3^2\).
Aplicăm funcția totent pentru a afla numărul de valori prime cu acesta.
\(\phi(9)=9\cdot(1-\frac{1}{3})\)
\(\phi(9)=6\) => 6 valori sunt prime cu acesta.

O implementare în C++:

int Indicatorul_Euler(int n)
{
    int i,euler=n;
    if(n==1) //Caz special cand n=1 returnam 0
        return 0;
    if(n%2==0) //Singurul nr prim par 2...
    {
        euler -= euler/2; //Aplicam formula lui euler de mai sus.
        while(n%2==0)
            n/=2;
    }
    for(i=3; i*i<=n; i+=2) //Factorii sunt primi deci daca am gasit 2 ca fiind factor prim, acela fiind singurul par, cautam doar cei impari
    {
        if(n%i==0)
        {
            euler -= euler/i; //De asemenea...
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        euler -= euler/n;
    return euler;
}