[FLUG] Re: [CODE] Re: Internet time
- From: "Simon" <seddie@xxxxxxxxx>
- To: <fanolug@xxxxxxxxxxxxx>
- Date: Sat, 15 Mar 2003 13:43:25 +0100
Mailing List del Fortunae LUG
=============================
> > Non so... dimmi cos'hai capito.
>
> numeri primi?
Si. Dunque non ho trovato la dimostrazione matematica per cui
basterebbe scorrere fino a sqrt(h) e non ho avuto voglia di pensarci :-)
Però pare funzionare.
Comunque sia ci sono un sacco di trucchetti da implementare nell'algoritmo
per renderlo più veloce (primo fra tutti saltare tutti i numeri pari...
ponendo l'incremento a +2 per numeri >= 3).
Ti basti sapere che chi ci lavora sul serio su queste cose... come Chongo
(http://www.isthe.com/chongo/index.html una pagina assolutamente
da visitare... sto tizio è un mito!!!!) per esempio usano GIMPS che usa
delle librerie matematiche a 64 bit o più (che però girano sui 32bit... cosa
rullante... bei trucchetti in asm).
Il numero primo più grande scoperto al momento è (2^13466917)-1.
(e non è stato scoperto grazie alla mia sign :-)
C'è un altro teorema che dice che basta controllare che un numero non
sia divisibile solo per i numeri primi che lo precedono. E un sacco
di altri trucchetti.
Il mio algoritmo rispetto a queste raffinatezze è un brute-force... non si
scoprono così i numeri primi :-) Diciamo che era l'implementazione papale
papale della definizione di numero primo... e come spesso accade in
questo genere di cose l'implementazione della definizione non è l'algoritmo
più performante. Quello che volevo comunicare era "il concetto di numero
primo"... non l'algoritmo performante per trovarli.
Comunque sia, detto questo... grazie del suggerimento... vedrò se riesco
a farla "pareggiare" con i sqrt(h) al posto dei h/2 ;-)
PS. Se trovi la dimostrazione matematica del perchè, o se sai spiegarmelo
a parole tue... mi farebbe piacere.
Simon.
--
Bill Gates : "No! Nel nostro software non ci sono bug significativi che un
numero significativo di utenti vuol vedere corretti."
Other related posts:
