imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono
imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono
Last Exile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Unknowns
Nuida FollettoInLutto Bard Tiarna . . . . . . . . . . . . . . . . Deo The Undaunted Rune Priest
Amiag Blademaster Silver Hand. . . . . . . . . . . . . . Viol The Sacrificed Shadow Warrior
Viola Vampiir Grove Protector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nero Incubus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DarkBane
Naida Cabalist Phoenix Knight. . . . . . . . . . . . . . . . . . . . . . . . . . . . Viole No-Stealth Scout
quali?Originally Posted by Amiag
" ...e mai un pensiero non al denaro, non all'amore né al cielo... " Fabrizio de Andrè
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
Last Exile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Unknowns
Nuida FollettoInLutto Bard Tiarna . . . . . . . . . . . . . . . . Deo The Undaunted Rune Priest
Amiag Blademaster Silver Hand. . . . . . . . . . . . . . Viol The Sacrificed Shadow Warrior
Viola Vampiir Grove Protector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nero Incubus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DarkBane
Naida Cabalist Phoenix Knight. . . . . . . . . . . . . . . . . . . . . . . . . . . . Viole No-Stealth Scout
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!
Realm Of Trollers
while ( ! ( succeed = try() ) );
Spoiler
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?
" ...e mai un pensiero non al denaro, non all'amore né al cielo... " Fabrizio de Andrè
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?
" ...e mai un pensiero non al denaro, non all'amore né al cielo... " Fabrizio de Andrè
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
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
Last edited by dariuz; 19th November 2011 at 16:53.
-He who makes a beast of himself, gets rid of the pain of being a man
-I pity those that don't drink, for when they wake up in the morning, thats as good as they're going to feel all day!
-Silence is golden but duct tape is silver
Posting Permissions
Reply With Quote
