Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Notice Board

Problema di tempo eccessivo nella ricerca dei divisori

A
Andrea Bisaccia (800 points)
3 10 19
in Es1 by (800 points)
closed by
Buonasera, svolgendo il primo programma mi sono imbattuto in un problema di velocità di esecuzione. Ovvero, il programma gira perfettamente per il test con “numeri piccoli” mentre va abbondantemente oltre il time out per i “numeri grandi”.

Il problema è nella divisione ricorsiva di un numero che eseguo per cercarmi i divisori propri di ogni numero....probabilmente sto sbagliando approccio ma non ne vedo altri per arrivare ad avere tutti i divisori.

Ringrazio in anticipo per le risposte!
1.7k views
closed with the note: Answered

6 Answers

Best answer
F
FrancescoSanetti (1130 points)
2 4 11
by (1.1k points)
selected by
Per diminuire ancora di più le iterazioni basta iterare fino alla parte intera della radice più uno, del numero in questione, aggiungendo due al contatore dei divisori per ogni divisore trovato, per includere il fattore corrispondente: che altrimenti non verrebbe considerato perché maggiore della radice quadrata del numero.
L
Leop (450 points)
4 8 14
by (450 points)
secondo me hai ricevuto troppi pochi upvote per una risposta così chiara...
Il mio tempo di esecuzione è passato da KeyboardInterrupt dopo 2+ minuti a poco più di un secondo!
F
FrancescoSanetti (1130 points)
2 4 11
by (1.1k points)
Fa niente :)
Auron (15880 points)
50 126 194
by (15.9k points)
Ho letto il commento precedente al tuo Francesco, e pur avendo il tempo più basso di tutti perché ci sono arrivato per conto mio, sono d'accordo con Leop, ti voto anch'io!
Auron (15880 points)
50 126 194
by (15.9k points)
La nostra petizione ti ha portato alla miglior risposta, evvai!!!
F
FrancescoSanetti (1130 points)
2 4 11
by (1.1k points)
Grazie (y)(rofl)
S
Simone99_ (1180 points)
22 50 60
by (1.2k points)
edited by
ciao, non ho capito cosa intendi per aggiungere 2 al contatore dei divisori, perchè questa operazione?

*problema risolto, grazie mille a tutti!*
Jury Francia (7520 points)
23 76 100
by (7.5k points)
Ciao, avevo il tuo stesso problema all'inizio poichè dividevo il numero per tutti i numeri fino a se stesso, il che era inutile perché basta dividere i numeri fino alla metà del numero stesso, ma comunque questo metodo richiede molto tempo di esecuzione dato che deve effettuare molti calcoli. Ti consiglio di fare sicuramente qualche controllo, ad esempio puoi vedere se un numero è pari e divisibile per 2 etc, così eviti calcoli inutili.
Auron (15880 points)
50 126 194
by (15.9k points)
Esattamente :)
A
Andrea Bisaccia (800 points)
3 10 19
by (800 points)
La soluzione di partire dalla metà del numero l’avevo già implementata.
Ora sono arrivato alla conclusione che probabilmente devo prima dividere per 2, 3,5,7 così da levarmi poi tutti i loro multipli riducendo di molto i calcoli....
Jury Francia (7520 points)
23 76 100
by (7.5k points)
Esatto, prima di entrare nel ciclo che esegue la divisione vedi se un numero è divisibile per un certo divisore e successivamente puoi dividerlo per i suoi multipli, così risparmi molto tempo. Attento ad una cosa, che è successa a me, per quanto riguarda i numeri primi può succedere che facendo le divisioni per i multipli non trovi sempre i divisori di un numero e quindi potrebbe darti 0 divisori e quindi riconoscerlo come un numero primo, mi è successo con un numero molto alto il cui unico divisore era 881 se non sbaglio che è un numero primo. Quindi per i numeri primi dovresti fare qualche altro controllo.
Auron (15880 points)
50 126 194
by (15.9k points)

Ti copio come ho risposto ad un altro post uguale (ATTENZIONE A NON CHIEDERE COSE GIA' CHIESTE CHE SI INTASA IL FORUM :D)

Hai impostato un ciclo che si ripete n volte che controlla se n sia divisibile per l'indice del ciclo... Ora, per numeri medi e piccoli, la macchina ti sostiene (in maniera più o meno accettabile)... Ma tu immagina, per i numeri grandi, di essere nell'ordine di 50/60 miliardi... Ecco, adesso immagina che tu stai chiedendo computer di gestire un ciclo che viene ripetuto 60 miliardi di volte per il numero 6437635961, più 50 miliardi di volte per il numero 5311430407... e così via... Puoi capire da te che se la macchina potesse parlare ti direbbe "Amico mio, io te lo faccio questo conto, ma mi prendo il tempo che mi serve"... che non è poco... L'unica cosa da fare è prevedere dei controlli aggiuntivi che ti permettano di ridurre il numero di cicli e/o di numeri da controllare, in modo da abbassare drasticamente il tempo di esecuzione...

Consiglio: Una delle possibilità è quella di poter dimezzare il tempo di esecuzione per ben due volte, con due controlli diversi (puoi trovare più informazioni su un altro mio post in questo forum... e già il fatto di "dimezzare" dovrebbe farti avere qualche idea)...

Ma questo è solo uno dei controlli, io ne ho implementati anche altri... fai delle prove, divertiti a sperimentare e vedrai che scoprirai nuovi modi di vincere sulla macchina ;)

Spero possa aiutarti il consiglio, per iniziare :)

Denis (2230 points)
4 13 23
by (2.2k points)
Ciao,
Come hai già intuito, stai sbagliando approcccio.
L'algoritmo è corretto, nel senso che ti restituisce un corretto risultato, ma non ottimale.
Ci sono almeno due ottimizzazione che puoi fare, prova a rispondere a queste due domande:
Mi serve sempre, in ogni caso, sapere esattamennte quanti e quali sono i divisori?
Esiste un metodo diverso per calcolare i divisori di un numero?(e su questa ti consiglio di cercare bene in questo forum + in rete)
V
Vlad (4580 points)
2 14 24
by (4.6k points)

Vedo che hai già ricevuto degli ottimi consigli, aggiungo solo una cosa: possiamo evitare di arrivare fino alla metà di un numero quando in realtà basta arrivare alla radice quadrata. Ovviamente poi bisogna anche prendere in considerazione la velocità di esecuzione di sqrt in python, però è sicuramente qualcosa da tenere a mente.

gianpcr (4620 points)
5 16 34
by (4.6k points)
edited by
Ciao, devi cambiare approccio al problema. Ti consiglio di vedere le proprietà della scomposizione in fattori primi. Infatti tra le proprietà una è particolarmente utile: preso un numero per esempio 10, la sua scomposizione in fattori primi equivale a 2 * 5. Se sommiamo uno ad entrambi gli esponenti e li moltiplichiamo tra loro otteniamo 4, ovvero il numero di divisori di 10. Quindi in generale, se chiamiamo a,b,c... gli esponenti dei numeri primi della scomposizione di un dato numero n, il numero dei suoi divisori è dato dalla formula (a + 1) * (b + 1) * (c + 1) ecc.. Se implementato bene, l'algoritmo dovrebbe girare relativamente più veloce rispetto all'attuale. Spero di averti aiutato :)
V
Vlad (4580 points)
2 14 24
by (4.6k points)
Ciao gianmarco, innanzitutto grazie per aver scritto di questa proprietà, non la conoscevo.
Però non mi è chiaro il funzionamento, forse mi sta sfuggendo qualcosa di ovvio:
"Se sommiamo uno ad entrambi gli esponenti e li moltiplichiamo tra loro otteniamo [...] il numero di divisori"
poi dici
" in generale, se chiamiamo a,b,c... i numeri primi della scomposizione di un numero n, il numero dei suoi divisori è dato dalla formula (a + 1) * (b + 1) * (c + 1) ecc.."

Il mio dubbio è: non dovremmo sommare 1 agli esponenti di a,b,c?
gianpcr (4620 points)
5 16 34
by (4.6k points)
Ciao si ho sbagliato a scrivere, scusami. A,b,c sono gli esponenti
gianpcr (4620 points)
5 16 34
by (4.6k points)
Il problema ora si sposta sul trovare un modo efficace per fattorizzare un numero. Puoi per esempio prepararti una lista di numeri primi all'inizio del programma, così che non dovrai più calcolarli. Un ottimo metodo (anche se dispendioso in termini di memoria) è il "Crivello di Eratostene". Se vai su wikipedia trovi una spiegazione al riguardo. Altrimenti puoi procedere con altri modi, dipende dal modo in cui vuoi risolvere il problema
V
Vlad (4580 points)
2 14 24
by (4.6k points)
Ottimo, grazie mille per l'idea