Dându-se un număr natural n, să se afișeze pe ecran divizorii primi ai acestuia, precum și puterile din descompunere.
Exemplu. Pentru n = 20, se va afișa 22, 51 (deoarece 20 = 22 * 51 = 4 * 5).
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 adăugăm la descompunerea noastră, la final, n1.
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
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
int putere = 0;
while(n % d == 0) { //Cât timp se împarte n la acest divizor, creștem puterea
putere++;
n = n / d;
}
cout << d << "^" << putere << " ";
}
}
if(n > 1) { //Caz particular, când n mai conține un număr prim la final
cout << n << "^1";
}
return 0;
}