Știm din teorema fundamentală a aritmeticii că orice numar natural nenul poate fi scris ca un produs de numere naturale prime. Scrierea acestuia ca un produs de numere prime se numește descompunere în factori primi.

De exemplu, numărul \(126\) poate fi scris ca \(2\cdot3^2\cdot7\).

Poate v-ați întrebat de ce 1 nu se consideră a fi număr prim. Fiindcă dacă acesta ar fi prim, ar fi existat două reprezentări diferite a unui număr ceea ce nu respectă enunțul teoremei de mai sus.

De exemplu pentru numărul 15 ar fi fost considerate corecte următoarele descompuneri:
\(15=1\cdot5\cdot3 \)
\(15=1^2\cdot5\cdot3 \)
etc.

Acestea nu respectă teorema de mai sus fiindcă există doar o singură reprezentare corectă: \(15=5\cdot3\)

Pentru a afla descompunerea, vom implementa următorul algoritm:

• Cât timp numărul n introdus este mai mare sau egal cu 1:
  1. Căutam un factor prim d ce se află intre intervalul \([2,n]\)
  2. Număram de câte ori se imparte factorul prim găsit la n determinand astfel puterea.
  3. Dacă d îl depăsește pe \(\sqrt{n}\), constatăm că după operațiile efectuate n este prim și acesta este factor prim in descompunere.

Implementare în C++

#include <iostream>

using namespace std;

int main()
{
    /*
    Notatii:
    n - numarul citit
    d - factorul prim
    e - exponentul factorului prim */
    int n,d,e;
    cin>>n; //Citim numarul pe care dorim sa il descompunem
    d=2;
    while(n>1)
    {
        e=0;
        while(n%d==0)
        {
            n/=d;
            e++; //Numaram de cate ori se imparte (exponentul factorului prim)
        }
        if(e>0)
            cout<<d<<" "<<e<<'\n'; //Afisam factorul si exponentul acestuia
        if(d*d>n) //d>radical(n) <==> d*d>n (am ridicat la patrat expresia)
            d=n;
        else
            d++;
    }
    return 0;
}

Puteți vedea aplicații ale descompunerii în factori primi aici.