numeri primi

imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono

Quote:

---

Originally Posted by Amiag

imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono

---

quali?

http://it.wikipedia.org/wiki/Crivello_di_Eratostene

o per roba piu complessa

http://www.dti.unimi.it/citrini/MD/S.../algoritmi.htm


30 secondi

tra l'altro potresti usare la programmazione dinamica per salvare i risulatati parziali e non rifare gli stessi calcoli. se riesci a ridurre il numero dei calcoli fai come una scheggia!

Dato che sapere se il numero è primo è solo il primo step e quello che vorrei creare è ua omna sorta di programmino dinamico e aggiornabile la soluzione che mi consigli l'ho già implementata. Ho considerato un caso base(lancio il programma su un pc nuovo) in cui passo i primi 5 numeri primi, cosa che mi serve per andare a regime. Tutte le chiamate successive mandando anche il vettore dei evcchi numeri primi e eventualmente qualora per fare il test ne scopro altri riaggiorno il tutto. Quindi la problematica computazionale non è piu assoluta ma relativa. ORa mi leggo il tuo link. Il crivello di eratostene nn è utile per cercare numeri primi grandi. Ci sono altri metodi che mi sto studiando e sto cercando di capire... qualcuno mi spiega perchè miller rabin funziona in parole povere?

mi dite se ho capito giusto?
Prendo n da testare.Faccio n-1. Lo divido tante volte finche n-1/2 non da resto. Alche trovo una scomposizione del tipo
n-1=2^s * d
Scelgo un a primo a caso, scelgo per semplicità 2
a^d (modn)== 2^d modn = 1 il numero non è sicuramtne primo
!=1 il numero potrebbe essere primo
Giusto?

scegli i numeri fino a N, prendi un n e cominci a dividerlo per tutti gli interi compresi fra 2 e RADQ(N) e calcoli il resto, se il resto è sempre diverso da 0 hai un numero primo.
è la versione da bambini :nod:

altrimenti questo dovrebbe essere una specie di quello attualmente in uso (un elaborazione del test di fermat)

http://en.wikipedia.org/wiki/AKS_primality_test