Descompunerea în factori primi

Descompunerea în factori primi se bazează pe Teorema fundamentală a aritmeticii: Orice număr natural n mai mare decât 1 se poate scrie în mod unic sub forma \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), unde \( p_1 < p_2 < … < p_k \) sunt numere prime, iar \( e_i > 0, i=1..k \)

Exemplu: \( 140 = 2^2 \cdot 5^1 \cdot 7^1 \)

Pentru a determina descompunerea, vom proceda deductiv:

Program C++:

#include <iostream>
using namespace std;
int main(){
	int n;
	cin >> n;
	int d = 2,	// d va fi, pe rand, fiecare factor prim din descompunere
		p;		// p va fi puterea lui d in descompunere
	// il  impartim pe n la d in mod repetat, pana cand devine 1
	while(n > 1)
	{
    	if(n % d == 0) // d este divizor al lui n, deci factor prim al acestuia
        {
            // numaram de cate ori se imparte n la d. Aceasta va fi puterea lui d in descompunere
            p = 0;
            while(n % d == 0)
            {
                ++p;
                n /= d;
            }
			cout << d << " " << p << endl;
        }
		++ d;
		//	daca d * d il depaseste pe n si n nu este 1, decidem ca n este prim,
		//	si este factor in descompunerea valorii initiale a lui n
		if(n>1 && d * d > n){
			d = n; // trecem direct la n, urmatorul factor din descompunere
		}
	}
	return 0;
}

Programul de mai sus afișează pentru n descompunerea în factori primi; pe fiecare linie se afișează perechea factor putere. Merită observat că nu se parcurg toate numerele de la 1 la n. Dacă la un moment dat se decide că valoarea curentă a lui n este număr prim, se trece direct la aceasta, fără a mai parcurge un șir lung de numere care nu mai pot fi factori primi ai lui n.

Acest articol prezintă trei aplicații interesante ale descompunerii în factori primi!