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

In questo thread chiunque può postare un numero primo, specificando anche il numero di sequenza di tale numero (per es. 5 è il 3° numero primo).

Vediamo quale è il numero più alto che riusciamo a raggiungere... ovviamente lo scopo di questo thread non è cercare su un libro o andare sul sito di un centro di calcolo e fare copia incolla di un numero di 500 cifre...
lo scopo è mettersi alla prova, con programmi scritti da noi e con le capacità di calcolo dei NOSTRI processori per capire davvero quanto è grande l'infinito.

Per cui faccio affidamento sull'onestà di tutti! (a parte che con 2 conti si capisce se il numero ha richiesto 2 ore di calcoli di un Cray o di un qualsiasi pc..)

Che la gara abbia inizio!

183.324.667 è circa il 10milionesimo numero primo (credo!!! sto cercando di verificare)

intorno ai 28 milioni c'è 443782429 che (spero) sia primo

secondo me sarebbe interessante trovare l'algoritmo migliore (in termini di velocità confrontando quelli postati dagli utenti e provandoli sulla stessa macchina...

l'algoritmo migliore... ehehe
l'algoritmo migliore che mi viene in mente consisterebbe nel:
-prendo un numero n di cui voglio stabilire la primalità (sidice così?)
- lo divido per TUTTI E SOLI i numeri primi MINORI DI RADICE DI N

la cui implementazione ha il difetto che man mano che i numeri crescono cresce anche l'utilizzo della memoria.
la complessità computazionale però sarebbe O((log n)^1/2) (correggetemi se sbaglio)

l'algoritmo (semplicissimo) che ho implementato io consiste in:
-prendo un numero n di cui voglio stabilire la primalità (sidice così?)
-divido n per tutti e soli i numeri maggiori di 1 e minori di radice di n

questo porta a compiere dei calcoli completamente inutili ma ha un utilizzo della memoria pari praticamente a zero. come dire: ogni cosa ha i sui pregi e i suoi difetti
la complessità computazionale è quindi O((n)^1/2)

se invece l'ipotesi di riemann fosse vera basterebbe verificare x ogni numeri che esso sia effettivamente una radice NON BANALE di tale funzione!

Ehm.. non ho capito, potresti postare qualche link sulla radice di N perchè non ho la più pallida idea di cosa stai dicendo

Secondo me si potrebbero anche implementare i criteri di divisibilità (per 3,per 7,per 11,per 10n-1), penso che si risparmierebbe un bel po' di calcolo se il numero non è primo...

con radice intendo radice quadrata... ovviamente! cerca su wikipedia!

e questa frase
- lo divido per TUTTI E SOLI i numeri primi MINORI DI RADICE DI N
è la stessa cosa che hai detto tu... ma un po' meglio, xche x esempio 9 non è primo e se un numero è divisibile per 9 lo è di sicuro anche x 3

in effetti tempo fa pensai a un criterio universale di divisibilita' ( che tra l'altro, usato per 2, 3, 5, ecc. si riconduce a quelli gia' noti ), e' un po lungo da spiegare, e comunque e' un po' laborioso e, tranne che in qualche caso particolare o con numeri di centinaia di cifre, si fa molto prima a fare la divisione.

Per quanto riguarda il problema principale, se vogliamo trovare i numeri primi fino a X (con X grande "a piacere", e se vogliamo abusare della memoria, si puo' procedere cosi':

1) considero un array con tutti i numeri da 2 a X;
2) considero un indice i sul primo elemento dell'array;
2) prendo dall'array l'elemento n di posto i
3) elimino dall'array (conservando le posizioni vuote) tutti i numeri che incontro, partendo dalla posizione i, saltando di n posizioni alla volta (ossia tutti i numeri divisibili per n)
4) incremento i fino alla prossima posizione non vuota
5) se i non e' arrivato alla posizione X riprendo dal punto (2)

alla fine i numeri che rimangono nell'array saranno tutti e soli i numeri primi compresi tra 2 e X.

Computazionalmente non so... vedete voi.

Ciao.

Luigi