java筛网中的奥斯汀大于int

Question

我想找出100亿以下的所有素数。它是int所能容纳的5倍（这是数组的限制，无论类型如何）。试图一次分配超过12亿的内存会导致堆外空间错误。我尝试使用列表而不是布尔数组，但是ArrayList的set-element方法只索引到int。让我感到不安的是，很快就有不到整数的元素没有被删除。一种可行的方法是创建一个包含10个数组的分区，然后将它们粉碎在一起。。。但那将是丑陋的。如果你有任何优雅的解决方法的建议，请告诉我。（使用Python lol除外）。我已经有了一个n^2/2暴力实现，但这需要很长时间才能运行，所以我真的想尽快解决这个问题。我的Sieve实现最多可工作12亿次，如下所示：

public class SieveEratosthenes {
private boolean[] nums;
public static void main(String[] args) {
    int n = 1000000;
    SieveEratosthenes s = new SieveEratosthenes(n);
    for(int i=0;i<s.nums.length;i++){
        if(s.nums[i]){
            System.out.println(i);
        }
    }
}

public SieveEratosthenes(int max){
    sieve(max);
}

private boolean[] sieve(int max){
    nums = new boolean[max+1];
    initFlags();
    for(int i=2;i*i<max;i++){
        for(int j=i*i;j<=max;j+=i){//cross off non-primes
            nums[j]=false;
        }
    }
    return nums;
}
private void initFlags(){
    if(nums != null&&nums.length>1){
        nums[0]=false;
        nums[1]=false;
        nums[2]=true;
    }
    for(int i=3;i<nums.length;i++){
        nums[i]=true;
    }
}

public List<Long> sieveToList(){
    List<Long> sieveList = new ArrayList();
    for(int i=0;i<nums.length;i++){
        if(nums[i]){
            sieveList.add((long)i);
        }
    }
    return sieveList;
}

Answer 1

如果内存不是问题，请继续使用阵列，因为它速度更快。如果内存成为问题，我建议查看位集

虽然Java数据结构（据我所知）的最大int大小限制在20亿左右，但您可以创建自己的数据结构。一个非常简单的解决方案是创建一个类，根据max int length将请求的大小拆分为多个数组或位集，然后根据输入的长索引自动访问它们。我希望这是有道理的。如果你有任何问题，请告诉我

Answer 2

以下是您可以使用的一种方法：

• 使用10^7英寸或任何适合您的尺寸的筛子
• 然后，对于sieve的每个实现，最后，将所有计算出的素数保存在您熟悉的任何数据结构中（ArrayList也可以）
• 现在，使用循环（当然）进行1000次，每次，你们的筛子都会计算出下一个10^7范围内的素数。所以，在第一次迭代中，所有0-10^7的素数都会被计算出来。然后，从10^7+1到2*10^7，依此类推

PS：如果你想要代码，我会帮你做，但我建议你尝试一下。我可能在这方面错了，但我认为这种方法就是他们所说的segmented sieve

Answer 3

对此，您可能应该放弃使用数组。正如你所说，它们不适合非常大的一套。该算法的一个合理近似方法是，在检查每个素数时，通过测试它是任何先前素数的倍数来“划掉”。我还没有分析过它的性能

class Sieve {
    private long current = 2;
    private final List<Long> primes = new ArrayList<>();

    public long nextPrime() {
        while (primes.stream().anyMatch(p -> current % p == 0))
            current++;
        primes.add(current);
        return current;
    }
}