[FLUG] [CODE] Re: Internet time

Mailing List del Fortunae LUG
=============================

Simon wrote:

(http://www.isthe.com/chongo/index.html una pagina assolutamente

Grazie per il link, davvero interessante!

C'è un altro teorema che dice che basta controllare che un numero non
sia divisibile solo per i numeri primi che lo precedono.

Si: infatti se non e' divisibile per nessuno dei numeri primi che lo precedono, non puo' essere neanche divisibile per qualunque altro numero (minore di esso) che, se non e' primo, e' un prodotto di potenze di numeri primi...

Il mio algoritmo rispetto a queste raffinatezze è un brute-force...

Non volevo mica criticarlo! Solo che non capivo h/2! Forza bruta per forza bruta, mettevi h e via... :-)


PS. Se trovi la dimostrazione matematica del perchè, o se sai spiegarmelo
a parole tue... mi farebbe piacere.

Ci provo con parole mie :-)
Nel ciclo for in pratica dividi h per tutti gli interi g da 2 fino ad un certo limite, nella speranza di trovare che tutte queste divisioni abbiano resto diverso da zero.

Adesso pensa a quelle divisioni al contrario: h e' il prodotto di due numeri, uno dei quali e' il nostro g e l'altro e' appunto h/g che non si calcola. Se provi anche per g maggiore di sqrt(h), il secondo fattore e' sicuramente minore di sqrt(h) (perche' il loro prodotto deve essere h), e quindi l'hai gia' provato prima (la div e' commutativa...)!


Non so se si e' capito, ma e' + facile pensarlo che scriverlo :-)))

--
Andrea <andrea.b@xxxxxxxxx>

--
Bill Gates : "No! Nel nostro software non ci sono bug significativi che un numero 
significativo di utenti vuol vedere corretti."

Other related posts: