Implementazione Java di Sieve di Eratostene che può andare oltre n = 2^32?

Question

Attualmente questo generatore principale è limitato a n. < 2^32-1. Non sono completamente sicuro di come espandere ulteriormente il limite, dato il limite di elementi in un array.

Sieve:

public class Main { 

public static void main(String args[]){ 
    long N = 2000000000; 

    // initially assume all integers are prime 

    boolean[] isPrime = new boolean[N + 1]; 
    for (int i = 2; i <= N; i++) { 
     isPrime[i] = true; 
    } 

    // mark non-primes <= N using Sieve of Eratosthenes 
    for (int i = 2; i*i <= N; i++) { 

     // if i is prime, then mark multiples of i as nonprime 
     // suffices to consider mutiples i, i+1, ..., N/i 
     if (isPrime[i]) { 
      for (int j = i; i*j <= N; j++) { 
       isPrime[i*j] = false; 
      } 
     } 
    } 
} 
} 

Come potrei modificare questo di dribblare n = 2^32-1?

Answer 1

È possibile utilizzare un array di oggetti BitSet per rappresentare il set di bit lunghi.Ecco l'esempio completo:

public class Main { 
    private static class LongBitSet { 
     // max value stored in single BitSet 
     private static final int BITSET_SIZE = 1 << 30; 

     BitSet[] bitsets; 

     public LongBitSet(long limit) { 
      bitsets = new BitSet[(int) (limit/BITSET_SIZE+1)]; 
      // set all bits by default 
      for(int i=0; i<bitsets.length; i++) { 
       bitsets[i] = new BitSet(); 
       int max = (int) (i == bitsets.length-1 ? 
          limit % BITSET_SIZE : BITSET_SIZE); 
       bitsets[i].set(0, max); 
      } 
     } 

     // clear specified bit 
     public void clear(long pos) { 
      bitsets[(int) (pos/BITSET_SIZE)].clear((int) (pos % BITSET_SIZE)); 
     } 

     // get the value of the specified bit 
     public boolean get(long pos) { 
      return bitsets[(int) (pos/BITSET_SIZE)].get((int) (pos % BITSET_SIZE)); 
     } 

     // get the number of set bits 
     public long cardinality() { 
      long cardinality = 0; 
      for(BitSet bs : bitsets) { 
       cardinality += bs.cardinality(); 
      } 
      return cardinality; 
     } 
    } 

    public static void main(String args[]) { 
     long N = 4000000000L; 

     // initially assume all integers are prime 

     LongBitSet bs = new LongBitSet(N+1); 
     // clear 0 and 1: non-primes 
     bs.clear(0); 
     bs.clear(1); 

     // mark non-primes <= N using Sieve of Eratosthenes 
     for (long i = 2; i * i <= N; i++) { 
      if (bs.get(i)) { 
       for (long j = i; i * j <= N; j++) { 
        bs.clear(i * j); 
       } 
      } 
     } 
     System.out.println(bs.cardinality()); 
    } 
} 

Questo programma per N = 4_000_000_000L prende in giro 512MB di memoria, opere paio di minuti e stampe 189961812 che è corretto numero di primi di sotto di 4 miliardi according to Wolfram Alpha. Se hai abbastanza RAM, puoi provare ad impostare ancora più grande N.

Answer 2

vedo opzioni:

1. pacchetto 16 Intervallo/1 BYTE

   • ricordare i numeri dispari solo per ogni bit variabile senza segno
   • uso per evitare sprechi bit di segno

2. utilizzare più di 1 tavolo

   • ma in 32bit app si sono limitati dalle capacità del sistema operativo
   • solito 1/2/4 GB di memoria utilizzabile
   • così grande tavolo di solito non si adatta all'interno CACHE così non è molto veloce in ogni caso

3. è possibile utilizzare più si avvicina al tempo

   • combino setacci periodiche trovato lista privilegiata ricerca binaria
   • Se si sceglie le dimensioni destra si può anche migliorare le prestazioni
   • per meglio utilizzando le proprietà piattaforma di caching
   • vedere Prime numbers by Eratosthenes quicker sequential than concurrently?
   • l'idea è quella di utilizzare setacci per testare piccoli divisori
   • e solo allora verificare la presenza all'interno lista privilegiata
   • non sta richiedendo più di tanto la memoria
   • ed è pret ty veloce

4. per risparmiarvi la memoria è possibile combinare 16/32/64 variabili bit

   • uso piccola larghezza po ', mentre è possibile
   • così hanno lista privilegiata divisi a 3 gruppi: piccolo/medio/grande
   • se si desidera bigints anche aggiungerli come quarta lista

Answer 3

Puoi segmentare il setaccio: invece di allocare un singolo, gigantesco array alloca molti piccoli array. Se si desidera trovare i numeri primi fino a 10^10, è possibile utilizzare gli array (o, meglio ancora, BitSet s) di dimensioni 10^6 o giù di lì. Quindi esegui il setaccio 10^4 volte. Ogni volta che esegui un nuovo segmento devi scoprire da dove iniziare ogni primo nel setaccio, ma non è troppo difficile.

Oltre a consentire un utilizzo della memoria molto più piccolo, questo mantiene più memoria nella cache, quindi è spesso molto più veloce.