Dubbio su i numeri primi

Question

Buonasera e tutti,
volevo abbassare ancora di più il tempo di esecuzione del mio primo esercizio, mi ricordavo che di N non possono esistere divisori primi > N**0.5 , ma ho notato che non è propriamente vero.

Sto sbagliando qualcosa o ricordo bene?

Answer 1

no infatti non è vero... ma prendi un esempio

115 lo dividi per due e non va, poi per 3 e non va...fino a 5

quando lo dividi per 5 diventa 23, che è maggiore della radice, ma se noti bene, 23 che numero è?

in generale, se un fattore primo è maggiore della radice non può esistere UN ALTRO fattore primo maggiore della radice

questo perché per la scomposizione un numero deve essere uguale al prodotto di tutti i suoi fattori primi, quindi se ho a b c d come fattori, tutti a esponente 1 e la radice è b<rad<c va da se che c*d da un numero maggiore del numero di partenza, e quindi è impossibile

Comments

grazie mille hai risolto il mio problema =)

Answer 2

Ciao, cosa ti ha fatto notare che non è propriamente vero? Un metodo per diminuire il tempo di esecuzione è quello di salvarti in una lista tutti i numeri primi che calcoli ogni volta che richiami la funzione, così che alla prossima chiamata della funzione, prima di controllare se è primo verifichi se è già presente nella tua lista, evitando quindi calcoli inutili.

Comments

per esempio 8640829 la sua radice è 2939,52 ma un suo divisore primo è 3739

---

Certo ma comunque ti interessa trovarne uno che non sia uguale ad 1 o se stesso (in questo caso 8640829). Infatti tra i divisori di 8640829 trovi 2311 che è minore della radice del numero e ti consente di stabilire se il numero è primo o meno

---

guardate che per punizione vi faccio scrivere 1000 volte alla lavagna "divisore *proprio*"  :)

Answer 3

Ciao!

La tua affermazione è più che giusta ed è vera, cosa ti fa venire dei dubbi??
Ricorda ovviamente che tale concetto va sfruttato con altri piccoli meccanismi per ridurre il tempo d'esecuzione!

- Francesco Pio Scognamiglio

Answer 4

Qui non stiamo cercando i divisori primi, ma i divisori propri.

Comments

sisi professore, mi è venuto in mente un algoritmo, molto più lungo ed intricato, ma più efficente per trovare il numero dei divisori propri tramite i numeri primi

---

in questo modo invece che 2/3 secondi per i numeri grandi ho lo stesso risultato in 0.14 secondi