In un commento al post precedente mi si chiedeva se non era possibile cercare un numero primo di un milione di cifre semplicemente scrivendo tutti i numeri da 1 fino al numero candidato, e poi cominciando a togliere dall'elenco tutti i multipli di 2, poi i multipli di 3, poi quelli di 5, e via via così. Questo metodo effettivamente esiste, e si chiama crivello di Eratostene, ma non è un metodo molto efficiente.
Tra i numeri molto grandi, ne esistono alcuni che si prestano particolamente ad essere analizzati per vedere se sono numeri primi oppure no: si chiamano numeri di Mersenne, e si ottengono sottraendo uno ad una potenza di 2. Per questi numeri esiste un test di primalità molto veloce, che si chiama test di Lucas-Lehmer.
Per avere un'idea sulle differenze tra i due metodi, vediamo un esempio. Per controllare un numero di Mersenne con esponente intorno a 33 milioni (non è un numero scelto a caso: con quell'esponente si ottiene un numero di circa 10 milioni di cifre, numero minimo richiesto dalla EFF per il premio, in realtà ora stanno già testando esponenti intorno ai 37 milioni) il mio computer, non particolarmente nuovo e veloce, impiegherebbe due mesi. Un dual core ultimo modello magari impiega meno della metà, comunque non è un test che si fa in un momento. L'algoritmo usato richiede un numero di operazioni dell'ordine di p2ln(p), nel nostro esempio questo numero vale circa
19·1015 (19 milioni di miliardi di operazioni).
Bene, il crivello di Eratostene richiede invece un numero di operazioni dell'ordine del numero stesso, cioè 10107, cioè un numero che si scrive con dieci milioni di cifre. Poco meno di venti milioni di mesi, sul mio computer.
Esiste un sito (www.mersenne.org) che distribuisce la ricerca dei numeri primi di Mersenne sui computer dei volontari che vogliono contribuire. Se vi iscrivete, potrete far fare qualche test al vostro pc, quando è inattivo. Ma serve un pc che funzioni bene, il test mette a dura prova il sistema, e se c'è qualcosa che non va, tipo qualche banco di ram difettoso, se ne accorge e ve lo segnala.
[L'immagine in alto è animata, ma qua non si vede. Bisogna cliccarci sopra e aprirla in una nuova finestra]
3 commenti:
bello!
Finalmente un modo utile per fare uno stress-test after overclock!
io ho scritto un programmino facile facile che verifica se un numero è primo, e lo mette in una tabella, poi prende il successivo e verifica solo se è divisibile per un numero in quella tabella e solo fino alla sua radice quadrata.
Quindi se devo verificare se 53 è primo, verifico se è divisibile per 2, 3, 5, 7 e poi mi fermo, perché se fosse divisibile per 11, 13 ecc... sarebbe divisibile sicuramente anche per 2, 3, 5 o 7.
Così in un quarto d'ora ho ricavato circa 500.000 numeri primi.
poi ho pensato "e adesso?"
E mi sono risposto "PANINO CON NUTELLA!"
Per "pochi" numeri, è un metodo che funziona.
Posta un commento