Factorització

De Viquipèdia

La factorització és el procés de descomposar un nombre natural en un producte de nombres primers.

D'aquesta manera, qualsevol nombre passa a prendre la següent forma:

$x = 2^n\cdot 3^m\cdot 5^o\cdot 7^p\cdot 11^q\cdot 13^r\cdot ... \$

Per exemple:

$25=5^2 \$

$1960 = 2^3\cdot 5\cdot 7^2 \$

$512568377=17^5\cdot 19^2 \$

Donat que no existeix cap mètode general per saber si un nombre és primer o no, i a més la quantitat de nombres primers és infinita, resulta que la factorització és un dels problemes més difícils i a la vegada importants de l'aritmètica entesa tant com teoria de nombres com a camp més general.

[edita] Mètode per descomposar un nombre en factors primers

L'únic mètode que es coneix per factoritzar, consisteix en anar provant la divisibilitat d'un nombre per cadascun dels nombres primers que existeixen. Es comença provant pel 2, i després es segueix amb els primers immediatament superiors. Cada vegada que es troba un primer divisor, es divideix el nombre a factoritzar pel primer divisor, i es segueix cercant divisors primers per al quocient de la divisió. Aquest procés segueix fins que el quocient de la divisió és 1. Els factors primers són tots aquells pels quals s'ha dividit el nombre per arribar a 1.

Exemple:

2028/2=1014

1014/2=507

507/3=169

169/13=13

13/13=1

Per tant:

$2028 = 2^2\cdot 3\cdot 13^2 \$

A vegades un nombre primer resulta ser tant gran que hem de provar la divisibilitat amb molts primers per arribar a la conclusió de que aquest nombre és primer. Convé veure aquí que en cap cas, donat un nombre $x \$ , trobarem un factor primer més gran que $\sqrt{x} \$ .

[edita] Implementació en informàtica

Un codi senzill que retorna la factorització d'un nombre pot ser el següent

#include <iostream>


using namespace std;


int main() {
   int n, cn; //n i còpia de n
   while(cin >> n) {
       cn = n;
       int i = 2; // possibles divisors. l'1 no val.
       cout << n << " = ";
        
       while(n > 1) {
           if(n%i == 0) {
               if(n == cn) cout << i; //estem en el primer cas i no cal posar '*'
               else cout << "*" << i;
                
               n /= i;
               i = 2;
           }
           else ++i;
   }
   cout << endl;
   }
}