Eratosthenes筛选的Java实现可以超过n = 2 ^ 32？

Question

目前我有这个素数发生器,限制在n <2 ^ 32-1.鉴于数组中元素的限制,我不完全确定如何进一步扩展限制.

筛:

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

我怎么能修改这个以超过n = 2 ^ 32-1？

Answer 1

您可以使用对象数组BitSet来表示长位集。这是完整的示例：

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

该程序需要N = 4_000_000_000L大约 512Mb 的内存，运行几分钟并根据 Wolfram Alpha189961812打印出低于 40 亿的正确素数数量。如果你有足够的RAM，你可以尝试设置更大的N。