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

我看到选项：

pack 16 numbers / 1 BYTE
- 每个位只记住奇数
- 使用无符号变量避免符号位浪费
使用1个以上table
- 但在 32 位应用程序中，您受到 OS 功能的限制
- 通常为 1/2/4 GB 可用内存
- 这么大table通常放不进CACHE所以反正不是很快
一次可以使用更多方法
- 我将周期性筛选与找到的素数列表二进制搜索相结合
- 如果您选择合适的尺寸，您甚至可以提高性能
- 通过更好地使用平台缓存属性
- 见Prime numbers by Eratosthenes quicker sequential than concurrently?
- 想法是用筛子来检验小除数
- 然后才检查素数列表中是否存在
- 不需要那么多内存
- 而且相当快
为了节省内存你可以组合16/32/64位变量
- 尽可能使用小的位宽
- 因此将素数列表分为 3 组：small/medium/big
- 如果您还想要 bigints，请将它们添加为第 4 个列表

Answer 2

您可以使用 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 的内存，工作几分钟并打印 189961812 这是正确的素数低于 40 亿 according to Wolfram Alpha。如果你有足够的RAM，你可以尝试设置更大的N。

Answer 3

您可以对筛子进行分段：分配许多小数组而不是分配一个巨大的数组。如果你想找到 10^10 以内的素数，你可以使用大小为 10^6 左右的数组（或者更好，BitSets）。然后你运行筛 10^4 次。每次运行一个新片段时，您都需要找出筛子中每个素数的起始位置，但这并不难。

除了允许使用更小的内存之外，这会在缓存中保留更多的内存，因此速度通常要快得多。

Java 可以通过 n = 2^32 的埃拉托色尼筛法的实现？

Java implementation of Sieve of Eratosthenes that can go past n = 2^32?

java

algorithm

primes

sieve-of-eratosthenes