Divisori fino a radice quadrata di N ES2

Question

In termini di tempo non conviene cercare i divisori da 0 a N

Potrei cercarli da 0 a N/2 ma cosi è ancora molto lenta come ricerca

Ho letto che si possono cercare da 0 fino a sqrt(N) come è possibile?

Answer 1

Si è possibile ma ad ogni ciclo devi salvarti sia il numero che N/numero. Così ottieni due divisori ad ogni ciclo solo che poi devi eliminare gli eventuali doppioni...oppure li inserisci direttamente in un insieme così non c'è questo problema.

Comments

Puoi spiegarti meglio sulla parte "poi devi eliminare eventuali doppioni" gentilmente?

---

Si mi sono spiegato male...intendevo dire che applicando questo metodo si genera due volte uno stesso numero. Ti faccio un esempio:
divisori(16)
[1,16,2,8,4,4]
Come puoi vedere nell'output il 4 compare due volte perchè nell'ultimo ciclo svolto viene aggiunta alla lista sia 4 che 16/4 =4.
Un modo per risolvere questo problema è inserire il tutto in un set così da eliminare i doppioni...oppire eliminarli in altro modo dalla lista.
Spero di essere stato più chiaro...

Answer 2

Io l'ho fatto cosi. Ma i divisori non escono ordinati. Es ( 2,4,6,9). Ad ogni iterazione controlli se il numero modulo i da 0 e controlli anche per numero fratto i.

Comments

Con un controllo se è diverso da i

---

Se il numero i è un divisore di n anche n/i lo è (senza bisogno di controllare due volte) -> i*n/i = n