java - 筛选大于 int 的 Eratosthenes

Question

我想找出100亿以内的所有素数。这是 int 可以容纳的 5 倍(这是数组的限制，无论类型如何)。尝试一次分配超过 12 亿会导致堆空间不足错误。我尝试使用 List 而不是 boolean 数组，但是 arrayLists 的设置元素方法只能索引到 int。让我烦恼的是，很快进入筛子的元素数量不到整数，没有被划掉。一种可行的方法是创建一个包含 10 个数组的分区并将它们拼在一起……但这会很丑陋。如果您对解决此问题的优雅方法有任何建议，请告诉我。 (除了使用 Python 大声笑)。我已经有一个 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

这是您可以使用的一种方法:

• 使用 10^7 整数或适合您的任何大小的筛子。
• 然后，对于 sieve 的每个实现，最后，将所有计算出的素数保存在您熟悉的任何数据结构中(ArrayList 可以)。
• 现在，执行此操作 1000 次，使用循环(当然)，每次，您的筛子都会计算下一个 10^7 范围内的素数。因此，在第一次迭代中，将计算 0-10^7 中的所有素数。然后，从 10^7+1 到 2*10^7 等等。

PS:如果你想要代码，我会为你做，但我建议你尝试一次。我在这方面可能是错的，但我认为这种方法就是他们所说的分段筛。