Fattorizzazione in numeri primi.

Ogni numero si scrive, in modo unico, come un prodotto di numeri primi.
Per esempio: 12 = 2.2.3 = 22.3, 21 = 3.7, 36 = 22.32, ecc...
Questo teorema (già noto ad Euclide) è il teorema fondamentale dell'aritmetica e mette in evidenza l'importanza dei numeri primi: sono i mattoni con i quali sono costruiti tutti gli altri numeri.
Il programma permette di visualizzare o stampare su un file .rtf i fattori primi di un numero < 1.000.000.000. (La scrittura a^b sta per ab).
La dimostrazione dell'esistenza di una fattorizzazione in numeri primi non è difficile se si sa che ogni numero ammette almeno un divisore primo. Infatti sia p un divisore primo di n: n=pq. Se n=p, n è primo e abbiamo finito. Altrimenti 1 < p < n e q < n. Se q è primo abbiamo finito, altrimenti anche q ammette un divisore primo: q = p2q2. Abbiamo: n =pp2q2. Inoltre 1 < q2 < q < n. Adesso reiteriamo il procedimento con q2 e i successivi quozienti (otteniamo quindi: 1 < qi < ... < q2 < q < n). Però, siccome tra 1 e n ci sono solo n-2 numeri, il procedimento dovrà finire, cioè si arriverà ad un qj primo.
L'esistenza di un divisore primo si ottiene nello stesso modo: se n è primo, basta prendere n stesso, altrimenti, per definizione, n ammette un divisore, d, con 1 < d < n. Se d è primo, abbiamo finito, altrimenti d ammette un divisore, d2, con 1 < d2 < d < n. Procedendo così si arriverà inevitabilmente (perchè ci sono solo n-2 numeri tra 1 e n) a un di primo.
La dimostrazione dell'unicità della fattorizzazione è un pò più brigosa e non la riportiamo.

Il codice funziona così: prima si definisce una funzione (o metodo) di due variabili intere: Fact(N,d) tramite F(N,d) = la più grande potenza di d che divide N (in particolare F(N,d)=0 se d non divide N, perchè d0=1). Il codice (in Java) è:

    public int Fact(int N, int d){
    	int m=0;                                  //m è un contatore inizializzato a 0
    	if(N % d == 0){                           // se d divide N
    		while(N % d == 0){                // mentre d divide N
    			m += 1;                  //incrementa m di uno
    			N = N/d;}                //rimpiazza N con N/d; fine del ciclo while
    			}                        // fine del if
    		return m;}                       //restituisci m = Fact(N,d); fine del metodo

Dopodichè per ogni i, 2 < = i < =n, si valuta Fact(n,i)=m, se m=0, i non divide n, si incrementa i di uno e si ricomincia. Se m > 0, si mettono i e m in un "serbatoio", si rimpiazza n con n/im, si incrementa i di uno e si ricomincia.
Osservazione: Non ci si preoccupa di sapere se i è primo o meno! Infatti se d è il più piccolo divisore di n con d > 1, allora d è necessariamente primo. Se n2 = n/dm, allora nessun multiplo di d divide n2 e il più piccolo divisore di n2 maggiore di uno è > d ed è un numero primo, ecc... (pensate alla fattorizzazione: stiamo prendendo i primi della fattorizzazione in ordine crescente).
Si sarebbe potuto procedere così: per ogni i, 2 < = i < = n:
a) vedere se i è primo
b) vedere se i divide n e, se sì, "quante" volte i divide n
Il programma qui sopra è più efficiente.