Algoritmi - SFIDA: Chi posta il numero primo più alto?

scusa ho capito bene? Intendi

         1               10^148
--------------- = --------------- >> 1
 2 x 10^-140            2

ma una probabilita' non dovrebbe essere compresa tra 0 e 1?

Si, mi sono sbagliato, pensavo ad una cosa ed ne ho scritta un'altra. P(E)= 1/(2*10^148)

si, lo so.. avevo anche fatto un programma che determinava se un numero è primo o no usandeo il test probabilistico di rabin (è su questo sito, è fatto in java) e l'algoritmo mi sembrava effettivamente una cosa geniale.. il problema è che i risultati erano veramente ma veramente pessimi nonostante le probabilità parlassero chiaro..

2^43.112.609-1

L'algoritmo di rabin-miller è un test probabilistico molto buono. Si può abbassare a piacere la probabilità di errore reiterando il test quante volte si vuole.
L'algoritmo migliore per il test "deterministico", quindi con risposta assolutamente certa, è questo:

en.wikipedia.org/wiki/…

è l'unico test deterministico di primalità conosciuto ad avere complessità polinomiale. Tutti gli altri test deterministici (compreso quello che avete usato voi) sono di complessità esponenziale. Rabin-Miller è polinomiale ma è probabilistico.

Analizziamo il test di primalità basato sulle divisioni dei numeri da 1 a sqrt(n). Il numero di divisioni è O(sqrt(n)). Considerato che n ha un numero di cifre t in base 2 pari a t=log2(n), allora n = O(2^t). Quindi la complessità è O(sqrt(2^t)) = O(2^(t/2)). Saltando i numeri pari si arriva ad un miglioramento misero sui grandi numeri, pari a O(2^(t/2 - 1)). Ovviamente stiamo considerando costante il tempo necessario per fare le divisioni. L'algoritmo di euclide per le divisioni suggerisce inoltre che la divisione ha complessità lineare rispetto al numero di cifre, pari circa a O(5t), dove t è il numero di cifre di n. Quindi in totale la complessità dell'algoritmo è ancora peggiore, cioè O(2^(5t/2)).

NB: ho usato questa notazione per le formule: 2^(t/2) si legge "2 elevato t mezzi". sqrt(n) si legge "radice quadrata di n". log2(n) si legge "logaritmo in base 2 di n".


EDIT: per approfondire, leggete anche questo it.wikipedia.org/wiki/… si tratta della funzione PHI di eulero, che viene usata all'interno dell'algoritmo AKS

EDIT2: leggete anche questo en.wikipedia.org/wiki/… . Spiega l'algoritmo per le divisioni tra numeri interi. Per numeri molto grandi non si può usare la divisione della CPU, in quanto è limitata nel numero di bit (32, 64 o 128, in base all'architettura), quindi bisogna implementare questo algoritmo (che è uno dei più efficienti conosciuti ed è stato inventato duemila anni fa da Euclide).

Il mio script scrive in circa 30 sec i numeri primi fino a 100.000, poi si blocca

Qualcuno potrebbe sistemarlo? Grazie!

PS: ho rinominato da rar a zip la cartella con i sources

Ho trovato la soluzione, l'array che conteneva i numeri primi era troppo piccolo e si riempiva subito, poi le variabili si possono anche trasformare da integer a double, infine, invece di fare "+1" ad ogni giro while si può fare +2 ( tanto i numeri pari non potranno mai essere primi )

Qualche numero trovato con questo metodo? semplice! 2342623 2342633 2342657 2342663 2342671 2342677 2342687 2342723 2342731 2342741 2342771 2342773 2342777 2342779 2342783 2342797

altro test probabilistico:
teorema di fermat:
se n è primo e 0 < a < n,
allora a^(n-1) mod n = 1

nel 1981 Pomerance ha dimostrato che
se n èun numero casuale di 100 cifre e a è un numero casuale positivo minore di n,
la probabilità che n non sia primo e la formula restituisca ugualmente 1 è di 10^(-13)

ripetendo il test si abbassa a piacere questa (sgradevole) probabilità.
è anche l'algoritmo usato da openssl, se non sbaglio