Implementacja Java Sita Eratostenesa, która może przekroczyć n = 2^32?

Question

Obecnie mam ten główny generator, który jest ograniczony do n < 2^32-1. Nie jestem do końca pewien, w jaki sposób mógłbym zwiększyć limit, biorąc pod uwagę limit elementów w tablicy.

Sito:

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; 
      } 
     } 
    } 
} 
} 

Jak mogę zmodyfikować to przejść obok n = 2^32-1?

Answer 1

Możesz użyć tablicy obiektów BitSet do reprezentowania długiego zestawu bitów.Oto pełna przykład:

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()); 
    } 
} 

Ten program N = 4_000_000_000L zajmuje około 512 MB pamięci, działa kilka minut i druków 189961812 która jest prawidłowa ilość liczb pierwszych poniżej 4 miliardy according to Wolfram Alpha. Jeśli masz wystarczającą ilość pamięci RAM, możesz spróbować ustawić jeszcze większy N.

Answer 2

widzę opcji:

1. opakowanie 16 numerów/1 BYTE

   • zapamiętania liczb nieparzystych tylko za każdego bitu zmiennej unsigned
   • użycia w celu uniknięcia odpadów bit znaku

2. użycie więcej niż 1 tabela

   • ale w 32-bitowych aplikacji są ograniczone przez możliwości systemu operacyjnego
   • zwykle 1/2/4 GB pamięci użytkowej
   • taki duży stół zwykle nie pasuje wewnątrz CACHE tak to nie jest bardzo szybki i tak

3. można użyć bardziej zbliża naraz

   • Łączę okresowych sit znajdując prime lista binarnego wyszukiwania
   • Jeśli zdecydujesz rozmiary prawo można nawet zwiększyć wydajność
   • przez lepszego wykorzystania właściwości platforma buforowania
   • zobaczyć Prime numbers by Eratosthenes quicker sequential than concurrently?
   • pomysł jest użycie sita przetestować małe dzielniki
   • i dopiero wtedy sprawdzić obecność wewnątrz głównego listy
   • nie jest wymagający, że dużo pamięci
   • i jest pret Ty szybko

4. oszczędzić pamięć można połączyć 16/32/64 bitowe zmienne

   • użycie mały nieco szerokość póki możesz
   • więc nie prime lista podzielono na 3 grupy: mała/średni/duży
   • jeśli chcesz bigints również dodać je jako 4 listy

Answer 3

Możesz posegmentować sito: zamiast przydzielać pojedynczą, gigantyczną tablicę alokujesz wiele małych tablic. Jeśli chcesz znaleźć liczby pierwsze do 10^10, możesz użyć tablic (lub jeszcze lepiej, BitSet s) o wielkości 10^6 lub więcej. Następnie uruchamiasz sito 10^4 razy. Za każdym razem, gdy prowadzisz nowy segment, musisz dowiedzieć się, od czego zacząć sito w sicie, ale nie jest to zbyt trudne.

Oprócz umożliwienia użycia znacznie mniejszej pamięci, pamięć podręczna jest przechowywana w większej ilości, więc często jest znacznie szybsza.