[C] Scomposizione in fattori primi

[Manugal]

Ciao a tutti!

Devo scrivere un programma dove dato un numero n mi stampi la sua scomposizione in fattori primi. Non riesco a pensare ad un algoritmo funzionante. Voi che mi consigliate?

[Manugal]

Non fa niente.. ho trovato in rete il codice Java. Stavo impazzendo per farlo (anche se era semplice), cmq la mia idea c'andava vicino, perché io facevo ripetutamente la divisione per 2 però poi non sapevo gestire i casi successivi, cioè quando il numero non era più divisibile per 2. Grazie :)

[Ziosilvio]

In effetti... basta provare tutti i possibili divisori, e continuare a dividere finché si può.
Credo che la struttura dati più adatta sia una coda.

[Manugal]

Grazie Ziosilvio però alle liste, pile, code e strutture dati varie ancora non ci siamo arrivati (dobbiamo fare ancora gli array). Siamo proprio a un livello primordiale, quindi il programma andava fatto appunto a questo livello. ;)

[Ziosilvio]

Uhm... ripensandoci... puoi effettuare l'output a schermo "al volo", tanto deve venir fuori una cosa del tipo: "n = p1^e1 + p2^e2 + ... + pk^ek".
Praticamente:
- cominci stampando "n = ";
- trovi il primo fattore p1, che (se ci pensi un attimo) deve essere primo;
- dividi n per p1 tante volte finché puoi, tenendo il conto;
- stampi "p1^e1";
- se non ci sono altri fattori hai finito;
- se ce ne sono, osservato che il primo che trovi deve essere primo, fai come prima;
- stampi " + p2^e2";
e così via.

[Manugal]

Ok ma il primo fattore in base a quale criterio lo trovo? Cioè se n=18 ne ho tanti di numeri primi da trovare tra 1 e 18.

[cionci]

Inizi da 2 e sali su fino alla radice quadrata di n ;)

Continui a dividere fino a quando il resto della divisione è uguale a 0...

[repne scasb]

Ciao a tutti!

Devo scrivere un programma dove dato un numero n mi stampi la sua scomposizione in fattori primi. Non riesco a pensare ad un algoritmo funzionante. Voi che mi consigliate?

http://www.hwupgrade.it/forum/showpost.php?p=8744418&postcount=33

[Manugal]

Grazie ma perché fino alla radice quadrata di n e non fino a n?

[cionci]

Grazie ma perché fino alla radice quadrata di n e non fino a n?
Perchè ho sbgliato ;) Devi arrivare fino a n / 2... Supponendo k il divisore massimo di n allora n / k = j ====> j * k = n
Quindi per massimizzare k devo minimizzare j... Il minimo divisore diverso da 1 è 2... Quindi k <= n / 2...

Se non trovi fattori minori o uguali ad n / 2 allora n è primo...

[Ziosilvio]

Vero!
Il controllo fino a sqrt(n) va bene per determinare la primalità di un numero, perché se un numero n è composto, allora ha un divisore primo p tale che p^2 <= n.
Per determinare la decomposizione in fattori primi di un numero, la cosa è diversa (e NP-completa)...




... a meno, naturalmente, di non aggiornare volta per volta il numero da fattorizzare... ma qui dovrei provare a scrivere del codice...

[Manugal]

Ok grazie ho capito :D molto gentili