筛埃拉托色尼大于int

我要找出100亿以下的所有素数。这是int所能容纳的大小的5倍(这是数组的限制，无论类型如何)。尝试一次分配超过12亿个会导致堆空间不足错误。我尝试使用列表代替布尔数组，但数组列表的集合元素方法只索引到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;
}

您可以使用以下方法:

使用筛子筛选10^7 int或任何适合你的大小。
现在，这样做1000次，使用循环(当然)，每次，你的筛将计算下一个10^7范围内的质数。在第一次迭代中，所有0到10^7的质数都会被计算出来。然后，从10^7+1到2*10^7，以此类推。

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

您可能应该避免使用数组。正如你所说，它们不适合非常大的集合。该算法的一个合理近似是，在检查每个素数时，通过测试它是否为之前任何素数的倍数来"划掉"。我还没有分析它的性能。

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

如果内存不是问题，继续使用数组，因为它要快得多。如果内存成为一个问题，我建议查看BitSets。

虽然Java数据结构(据我所知)被限制在最大的int大小约为20亿，但您可以创建自己的数据结构。一个非常简单的解决方案是创建一个类，将请求的大小拆分为给定最大int长度的几个数组或bitset，然后根据您输入的长索引输入自动访问它们。我希望这能说得通。如果你有任何问题，请告诉我!

相关内容

最新更新

热门标签：