Quote:
Originariamente inviato da Scanca
Devo tenere in memoria i numeri primi da 0 a 8000000000 in Java.
Uso per generarli il crivello di Eratostene e li memorizzo con un BitSet.
Quindi il mio programma li deve generare, salvare e dare il numero di quanti sono.
Il problema è che non posso passare un numero più grande di 2000000000 perchè la classe BitSet accetta solo int.
Se dichiaro long x = 8000000000; mi viene segnalato un errore di range, come posso fare?
<cut>
|
Probabilmente ti hanno dato proprio dei limiti cosi' ampi per non permetterti di utilizzare strutture gia' pronte e vedere come te la cavi, soprattutto considerando che vai ad utilizzare una quantita' rilevante di memoria.
Ci sono parecchie soluzioni al problema: utilizzo di singoli bit per rappresentare l'informazione dentro/fuori il crivello (riduce il quantitativo di memoria, ma sembrerebbe ancora troppa, per te), bufferizzare su disco, ecc.
Secondo me, potresti dividere il tuo problema in intervalli piu' piccoli, per esempio parti di un milione (beh, potresti fare anche di piu', e' solo per capirsi).
Cominci considerando l'intervallo 0....999999 ed ottieni la lista dei numeri primi (che non e' lunghissima). Poi vai all'intervallo successivo ed elimini immediatamente i numeri primi gia' trovati, quindi applichi il crivello ai rimanenti, e cosi' via.
Non e' difficile da implementare, no?
Anzi, se poi vuoi rendere l'implementazione piu' eccitante, potresti notare che la fase di eliminazione dei numeri potrebbe essere svolta da piu' thread contemporaneamente. Ciascun thread potrebbe avere una sezione della lista da esaminare per eliminare i multipli.
Potresti implementare quindi un algoritmo per l'eliminazione parallela. Se stai usando Java 7 o successivo, potresti considerare l'uso delle primitive di Fork/Join, fatte appunto per problemi come questo.
Se usi Java 8, potresti tentare un'implementazione con i nuovi parallelStream