migliorare il codice per avere una divisione piu veloce in es2

Light (5130 points)
24 170 229
asked Oct 22, 2018 in Es2 by Light (5,130 points)
nel mio codice ho utilizzato per trovare i divisori un for che andava da 1 fino a quel numero e vedeva se quel numero che avevo era un divisore allora lo prendeva senno scartava; ma il problema è questa soluzione si funziona ma rallenta tantissimo il codice tanto che supero tutto nel grader ma in 30 secondi; ci sta un modo molto piu rapido per trovare i divisori magari senza usare un for?
380 views

5 Answers

Best answer
l
leoli (2930 points)
0 4 19
answered Oct 22, 2018 by leoli (2,930 points)
selected Oct 23, 2018 by Light
Per rendere più efficiente la tua ricerca dei divisori piuttosto che far andare il tuo for fino ad n potresti farlo andare fino alla radice di n e trovare due divisori per volta. Ti faccio un esempio: i divisori di 100 sono 1, 2, 4, 5, 10, 20, 25, 50, 100 ma li puoi associare a coppie (1,100) (2,50) (4,25) (5,20) (10,10) dove il secondo elemento è 100/ il primo -> puoi usare un divisore per trovarne un altro!
DRDLCN (8070 points)
3 67 104
answered Oct 22, 2018 by DRDLCN (8,070 points)
Si hai troppi for annidati, potresti definire una funzione divisori (che ti calcola i divisori di un numero n) e chiamarla al momento opportuno!
Light (5130 points)
24 170 229
commented Oct 22, 2018 by Light (5,130 points)
Si ci avevo pensato pero nel mio pensiero con sta funzione facevo una specie di scomposizione in fattori primi...poi non so se avendo questa posso trovare effettivamente i divisori
DRDLCN (8070 points)
3 67 104
commented Oct 22, 2018 by DRDLCN (8,070 points)
potresti chiamare la funziona che ti ritorna i divisori in una lista.
Esempio: funzione_divisori (6) ritorna una lista_divisori con dentro 2 e 3 e se vuoi anche il 6 e l' 1 , in base a cosa ti serve e in base a come stai lavorando.
Dopo di che iteri su lista_divisori
Light (5130 points)
24 170 229
commented Oct 22, 2018 by Light (5,130 points)
Quello si pero ti faccio un caso tipo 18 come nel testo 1 18 li prendo e li metto gia io nella soluzione 2 e 3 anche ma 4 6 9? E se nel numero tipo 14 ci fosse un numero primo tipo 7?
Light (5130 points)
24 170 229
commented Oct 22, 2018 by Light (5,130 points)
Oddio aspetta non avevo letto quel itera su lista_divisori cosi posso prendere anche i loro multipli right?
DRDLCN (8070 points)
3 67 104
commented Oct 22, 2018 by DRDLCN (8,070 points)
La funzione_divisori deve essere fatta in modo che se inserisci 7 ti ritorna 7 e 1 se ti servono entrambi o solo 7
Nel caso di 18 la funzione_divisori ti ritorna 1 2 3 4 6 9 18 li metti in una lista e ci iteri! Se ti servono li tieni se non ti servono li scarti
VincenzoImperati (6250 points)
1 11 54
answered Oct 22, 2018 by VincenzoImperati (6,250 points)
Per trovare i divisori di un numero N non è necessario che li cerchi fino a quel numero. I divisori ad esempio di 100 dopo 50 non ne trovi più. Finiscono sicuramente superata la metà del numero.  Oppure ancora meglio, Cerca i divisori di un numero N da 1 fino a radice quadrata di N compresa
Light (5130 points)
24 170 229
commented Oct 23, 2018 by Light (5,130 points)
ma scusa perche proprio fino a radice quadrata? nel caso di 18 che ha i divisori [1,2,3,6,9,18] la radice di 18 fa 4 qualcosa...cosi facendo non mi vede 6 e 9 no?
Light (5130 points)
24 170 229
commented Oct 23, 2018 by Light (5,130 points)
ma pure come dici te con 100 la radice quadrata fa 10..davvero non capisco sta cosa
VincenzoImperati (6250 points)
1 11 54
commented Oct 23, 2018 by VincenzoImperati (6,250 points)
Con la radice quadrata trovi due divisori alla volta
1
1824194 (1040 points)
3 15 23
answered Oct 22, 2018 by 1824194 (1,040 points)
potresti usare un while oltre ad un for che ti scorre nel range del numero a partire da 1 i numeri e confrontare con % quali sono divisori e danno resto zero e quali no e controllando quelli da prendere e scartare a sua volta
Sickboy (28240 points)
4 24 68
answered Oct 22, 2018 by Sickboy (28,240 points)
La cosa migliore e più veloce è scorrere i numeri da 2 a radice di N come gia ti hanno risposto gli altri su hai la spiegazione del perché fino a radice, puoi partire da due cosi ti metti gia nella lista risultante il valore 1 e il valore N
D
Deacoon (9100 points)
3 33 53
commented Dec 5, 2018 by Deacoon (9,100 points)
e togliere i for annidati