2^20996011-1 è primo!

[Antimateria]

Publio, log¹²x è sublineare! Tant\'è che quando il numero da testare ha più di 20 cifre, l\'algoritmo comincia a diventare MOLTO più efficiente di uno in tempo lineare!!

[pazqo]

ma la dimostrazione della primalità di 2^20996011-1 usa questo fatto?
<BR>come è stata fatta?

[publiosulpicio]

No, usa un altro algoritmo, su www.marsenne.org trovi tutti i dettagli.
<BR>Ma come sublineare? Io sapevo che se l\'algoritmo andasse come , ad esempio, n sarebbbe esponenziale, per una storia che la complessità è legata al numero di bit con cui si rappresente l\'imput, che è circa logaritmico... e quindi quando si parla di tempo lineare si parla di tempi che crescono come logn (e potenze varie), non come n... almeno così ho sentito dire... va bhè, mi informerò