
Afișarea divizorilor primi ai unui număr în C++
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;
}
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0