Per valutare se n è primo invece che dividere per tutti gli interi tra 2 ed n-1, ci si può fermare a radice quadrata di n ?
Per valutare se n è primo invece che dividere per tutti gli interi tra 2 ed n-1, ci si può fermare a radice quadrata di n ?
283
punti
Livello 1
Sì, certo.
Se provi per divisori che vanno oltre la radice di n, l'altro divisore dovrà necessariamente essere minore della radice di n, quindi lo avevi già esaminato...
Ricordo che mi posi la stessa domanda, quando da studente mi venne chiesto di scrivere un algoritmo di programmazione proprio per valutare se un numero è primo
4320
punti
Livello 6
8440
punti
Livello 7