02. Cicli annidati: scomposizione in fattori

Traccia:

Acquisire un numero naturale maggiore di 1 ed effettuare la scomposizione in fattori primi.

Strategia:

Il teorema fondamentale dell'aritmetica afferma che ogni numero naturale maggiore di 1 si può esprimere come prodotto di numeri primi (uno stesso numero primo può comparire più volte). Tale rappresentazione è unica, se si prescinde dall'ordine in cui compaiono i fattori.

Ad esempio 63 si può esprimere come 3*3*7.

Con lo scopo di mettere a punto un procedimento generale per la ricerca dei fattori primi di un qualsiasi numero, ricerchiamo i divisori del numero 63 procedendo per tentativi a partire dal numero 2:

    • 63%2 != 0 (cioè 2 non è divisore)

    • 63%3 == 0 (cioè 3 è divisore e quindi 3 è un fattore primo)

    • 63/3 == 21

    • 21%3 == 0 (cioè 3 è divisore e quindi 3 è nuovamente fattore primo)

    • 21/3 == 7

    • 7%3 != 0 (cioè 3 non è ulteriormente divisore)

    • 7%4 != 0 (cioè 4 non è divisore)

    • 7%5 != 0 (cioè 5 non è divisore)

    • 7%6 != 0 (cioè 6 non è divisore)

    • 7%7 == 0 (cioè 7 è divisore e quindi 7 è un fattore primo)

    • 7/7 == 1 (il quoziente vale 1 e quindi occorre fermarsi con la ricerca dei divisori)

Notare che nel procedimento descritto si avanza nella ricerca dei divisori in ordine crescente.

Quando un numero è divisore si effettua la divisione del numero e si effettua nuovamente la divisione a partire dal quoziente.

Procedendo in questo modo solo i numeri primi potranno risultare divisori.

Soluzione:


#include <stdio.h>

int main()

{

int i, N, quoziente;

printf("Inserire un numero N maggiore o uguale a 2: ");

scanf("%d", &N);

quoziente=N;

printf("Scomposizione in fattori primi: ");

for (i=2; i<=quoziente; i++) // La ricerca procede per ogni numero

while(quoziente%i==0){ // Verifica se i è divisore

quoziente/=i; // Effettua la divisione per i

printf("%d ", i);

}

return 0;

}