eddiewrc (Member)
Expert
 
Messaggi: 560
Iscritto: 30/04/2006
|
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!
|
|
|
eddiewrc (Member)
Expert
Messaggi: 560
Iscritto: 30/04/2006
|
183.324.667 è circa il 10milionesimo numero primo (credo!!! sto cercando di verificare)
|
|
|
eddiewrc (Member)
Expert
Messaggi: 560
Iscritto: 30/04/2006
|
intorno ai 28 milioni c'è 443782429 che (spero) sia primo
|
|
|
nick0 (Member)
Pro
Messaggi: 196
Iscritto: 19/10/2008
|
secondo me sarebbe interessante trovare l'algoritmo migliore (in termini di velocità) confrontando quelli postati dagli utenti e provandoli sulla stessa macchina...
|
|
|
eddiewrc (Member)
Expert
Messaggi: 560
Iscritto: 30/04/2006
|
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!
|
|
|
nick0 (Member)
Pro
Messaggi: 196
Iscritto: 19/10/2008
|
Postato originariamente da eddiewrc:
- 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)
|
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... |
|
|
eddiewrc (Member)
Expert
Messaggi: 560
Iscritto: 30/04/2006
|
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
|
|
|
gigisoft (Member)
Guru
Messaggi: 696
Iscritto: 11/10/2008
|
Postato originariamente da nick0:
Postato originariamente da eddiewrc:
- 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)
|
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... |
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 Ultima modifica effettuata da gigisoft il 26/02/2009 alle 16:08 |
|
|
eddiewrc (Member)
Expert
Messaggi: 560
Iscritto: 30/04/2006
|
beh geniale.. se fossi nato circa 2300 anni fa... in pratica stai parlando del crivello di eratostene!
cmq l'algoritmo attualmente migliore è il "number field sieve", cioè il crivello del campo numerico.
|
|
|
| 
