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;

}

Sito: 7ecnologie

Sezione: 08. C language

Capitolo: 02. Introduzione al C

Paragrafo: 09. Ciclo for

Approfondimento: 02. Cicli annidati: scomposizione in fattori

Indice dei capitoli: 00. Risorse - 01 Ambiente di sviluppo - 02. Introduzione al C - 03. Le librerie - 04. Tutorial - 05. Esercizi svolti - 98. Esercizi

Indice dei paragrafi: 01. Hello World - 02. Variabile di tipo int - 03. Input da tastiera - 04. Controllo condizionale if - 05. Operatori logici - 06. Ciclo while - 07. Operatore modulo - 08. Array - 09. Ciclo for - 10. Ciclo do/while - 11. Variabili di tipo float - 12. Funzione random() - 13. Impostazione del set di caratteri - 14. Definizione di funzioni - 15. Passaggio di parametri: gli array - 16. Variabili: visibilità e durata - 17. Il tipo char - 18. I file - 19. Funzioni matematiche

Indice degli approfondimenti: 01. Istruzione continue - 02. Cicli annidati: scomposizione in fattori - 03. Cicli annidati: screensaver