Divizibilitate / Descompunerea în factori primi


Editat de Candale Silviu (silviu) la data 2016-02-18
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!

Fișiere atașate


Vezi și:

Editat de Candale Silviu (silviu) la data 2016-02-18