筛分Eratosthenes大于int [英] Sieve Eratosthenes greater than int

问题描述

我想找到所有小于100亿的素数.这是int可以容纳的大小的5倍(这是数组的限制，与类型无关).尝试一次分配超过12亿，将导致堆空间不足错误.我尝试使用List而不是布尔数组，但是arrayLists的set元素方法仅索引到int.让我感到困扰的是，很快就会有少于整数个元素被划掉，进入筛子.一种可行的方法是创建一个由10个数组组成的分区，然后将它们粉碎在一起……但这很丑陋.如果您有解决此问题的优雅方法的建议，请告诉我. (除了使用Python大声笑).我已经有一个n ^ 2/2蛮力实现了，但是要花很长时间才能运行，所以我真的想尽快解决这个问题.我的多达12亿的Sieve实现如下:

I want to find all the prime numbers under 10 billion. Which is 5 times as big as int can hold (which is the limitation of arrays regardless of type). Attempting to allocate over 1.2billion at a time results in out of heap space error. I tried using List instead of a boolean array, but the set element method for arrayLists only indexes up to int. What bugs me, is that pretty quickly into the sieve there are less than an integer number of elements not crossed off. One method that should work, would be to create a partition of 10 arrays and smash them together... but that would be ugly. Let me know if you have any suggestions of an elegant way to solve this. (Other than using Python lol). I already have an n^2/2 brute force implementation, but that takes a long time to run so really I want to solve this as big O fast as possible. My Sieve implementation that works up to 1.2Billion is as follows:

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

推荐答案

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

Here is one approach that you can use:

• 使用10 ^ 7整数或任何适合您的尺寸的筛子.
• 然后，对于每个sieve的实现，最后，将所有计算的素数保存在您喜欢的任何数据结构中(ArrayList会这样做).
• 现在，使用循环(当然)执行此操作1000次，每次，筛子都会计算下一个10 ^ 7范围内的质数.因此，在第一次迭代中，将计算0-10 ^ 7的所有素数.然后，从10 ^ 7 + 1到2 * 10 ^ 7，依此类推.

PS:如果您想要该代码，我会为您完成，但是我建议您尝试一次.我对此可能是错的，但我认为这种方法就是他们所说的segmented sieve.

PS: If you want the code, I'll do it for you but I recommend you to try it once. I may be wrong on this but I think this approach is what they call segmented sieve.

这篇关于筛分Eratosthenes大于int的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！