Etichete: nicio etichetă

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:

  • știm că factorii primi ai lui n sunt cuprinși între 2 și n;
  • vom parcurge succesiv aceste numere și pentru un divizor curent d al lui n;
    • determinăm puterea sa în descompunere numărând de câte ori se poate împărții n la d. Această împărțire se realizează efectiv.
    • afișam divizorul curent d și puterea sa;
  • procesul se încheie când n devine 1.

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  im partim pe n la d in mod repetat, pana cand devine 1
	while(n > 1)
	{
		// 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;
		}
		// daca s-a facut cel putin o impartire, afisam factorul si puterea
		if(p)
			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!


Vezi și: