Numărul de divizori primi ai unui număr în C++

Dându-se un număr natural n, să se afișeze pe ecran numărul de divizori primi ai acestuia.

Exemplu. Pentru n = 20, se va afișa 2 (deoarece 20 = 22 * 51, adică are 2 divizori primi).

Explicarea algoritmului

Procedăm astfel: luăm primul divizor al lui n, asumăm că este un număr prim și îl împărțim pe n la el până când nu se mai poate (contorizând numărul de împărțiri). Astfel, am determinat primul divizor prim și prima putere (pe care le afișăm) și știm sigur că n acum nu se mai împarte la divizorul acesta. Repetăm procedeul cu următoarele numere, până când trecem de radicalul lui n.

De ce este divizorul curent mereu prim?

Se garantează că divizorul curent va fi prim. Să demonstrăm prin absurd: să zicem că întâlnim un divizor neprim al lui n, să îl notăm d. Numărul d, fiind compus (neprim), poate fi descompus ca produs de numere prime (pe care le-am notat p1, p2, …, pk):

Dacă n se împarte la d, înseamnă că n se împarte și la divizorii primi ai lui d, adică la p1, p2, …, pk. Cum aceste numere sunt clar mai mici decât d, înseamnă că le-am mai întâlnit înainte, când parcurgeam divizorii primi ai lui n. Dacă i-am întâlnit, înseamnă că l-am împărțit pe n la fiecare dintre aceste numere până când nu mai puteam, așadar n nu se mai împarte la niciunul dintre divizorii primi ai lui d. Așadar, n nu se poate împărți la d. Cum am zis că d este divizor al lui n, ipoteza este falsă, așadar toți divizorii d vor fi numere prime.

Alte observații

Este posibil ca și după parcurgerea cu for, să rămână o valoare în n. Această valoare va fi categoric un număr prim, așadar în acest caz adunăm 1 la numărul de divizori primi.

Implementare în C++

Iată rezolvarea în C++, folosind explicațiile menționate mai sus:

#include <iostream>

using namespace std;

int main()
{
    //Citim și declarăm numărul n
    int n;
    cin >> n;

    //Parcurgem divizorii primi
    int nrdivprim = 1;
    for(int d = 2; d * d <= n; d++) { //Începem de la 2, ne interesează doar divizorii primi
        if(n % d == 0) { //Am găsit un divizor prim
            nrdivprim++;
            while(n % d == 0) { //Cât timp se împarte n la acest divizor, îl împărțim pe n
                n = n / d;
            }
        }
    }
    if(n > 1) { //Caz particular, când n mai conține un număr prim la final
        nrdivprim++;
    }

    //Afișăm numărul răspuns
    cout << nrdivprim;
    return 0;
}